column

Open access

Efficient Graph Search

Author:

Terence KellyAuthors Info & Claims

Queue, Volume 18, Issue 4

Pages 25 - 36

https://doi.org/10.1145/3424302.3424304

Published: 13 September 2020 Publication History

All formats PDF

Abstract

Welcome to Drill Bits, a new column about programming. This inaugural episode shows how graph search algorithms can avoid unnecessary work. A simple modification to classic breadth-first search improves the lower bound on its running time: Whereas classic BFS always requires time proportional to the number of vertices plus the number of edges, the improved "Efficient BFS" sometimes runs in time proportional to the number of vertices alone. Both asymptotic analysis and experiments show that Efficient BFS can be much faster than classic BFS. All software used in the experiments is available for download, and suggestions for further explorations are provided.

References

[1]

Ahuja, R. K., Magnanti, T. L., Orlin, J. B. 1993. Network Flows (page 76). Upper Saddle River, NJ: Prentice Hall.

Google Scholar

[2]

Anderson, E., Tucek, J. 2010. Efficiency matters! SIGOPS Operating Systems Review 44(1):40?45; https://doi.org/10.1145/1740390.1740400.

Digital Library

Google Scholar

[3]

Boost graph library; https://dl.bintray.com/boostorg/release/1.73.0/source/boost_1_73_0.tar.bz2.

Google Scholar

[4]

Cormen, T. H., Leiserson, C. E., Rivest, R. L., Stein, C. 2009. Introduction to Algorithms, third edition (page 595). Cambridge, MA: MIT Press.

Digital Library

Google Scholar

[5]

Dijkstra, E. W. 1968. GOTO statement considered harmful. Communications of the ACM 11(3):147?148; https://doi.org/10.1145/362929.362947.

Digital Library

Google Scholar

[6]

GeeksforGeeks. Breadth-first search or BFS for a graph; https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/.

Google Scholar

[7]

McDowell, G. L. 2016. Cracking the Coding Interview, sixth edition (page 108). Palo Alto, CA: CareerCup.

Google Scholar

[8]

McSherry, F., Isard, M., Murray, D. G. 2015. Scalability! But at what COST? Usenix HotOS XV; https://www.usenix.org/system/files/conference/hotos15/hotos15-paper-mcsherry.pdf.

Google Scholar

[9]

Newman, M. 2010. Networks: An Introduction (page 320). New York, NY: Oxford University Press.

Crossref

Google Scholar

[10]

Orwant, J., Hietaniemi, J., and John Macdonald, J. 1999. Mastering Algorithms with Perl (page 307). O'Reilly.

Google Scholar

[11]

Sedgewick, R., Wayne, K. 2011. Algorithms, fourth edition (page 540). Addison-Wesley Professional.

Google Scholar

[12]

Wikipedia. Breadth-first search; https://en.wikipedia.org/wiki/Breadth-first_search

Google Scholar

Cited By

View all

Kelly T(2024)Zero Tolerance for BiasQueue10.1145/366464522:2(19-38)Online publication date: 29-May-2024
https://doi.org/10.1145/3664645
Kelly T(2024)Programmer Job Interviews: The Hidden AgendaQueue10.1145/363944421:6(16-26)Online publication date: 15-Jan-2024
https://doi.org/10.1145/3639444
Tarjan RZwick U(2024)Finding strong components using depth-first searchEuropean Journal of Combinatorics10.1016/j.ejc.2023.103815119(103815)Online publication date: Jun-2024
https://doi.org/10.1016/j.ejc.2023.103815
Show More Cited By

Index Terms

Efficient Graph Search
1. Computing methodologies
  1. Artificial intelligence

Index terms have been assigned to the content through auto-classification.

Recommendations

Efficient k-nearest neighbors search in graph space
Highlights
- The k-nearest neighbors (kNN) classifier is time consuming when the size of the database is large.
- We propose a fast k-nearest neighbor algorithm in graph space.
- The algorithm extends a Depth-First algorithm dedicated to solving ...
Abstract
The k-nearest neighbors classifier has been widely used to classify graphs in pattern recognition. An unknown graph is classified by comparing it to all the graphs in the training set and then assigning it the class to which the majority of the ...
A General Label Search to investigate classical graph search algorithms

Many graph search algorithms use a labeling of the vertices to compute an ordering of the vertices. We generalize this idea by devising a general vertex labeling algorithmic process called General Label Search (GLS), which uses a labeling structure ...
Decision Graph Search

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Queue Volume 18, Issue 4

Keys and Identity

July-August 2020

105 pages

ISSN:1542-7730

EISSN:1542-7749

DOI:10.1145/3424302

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 September 2020

Published in QUEUE Volume 18, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Badges

Qualifiers

Column
Opinion
Editor picked

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
26,178
Total Downloads

Downloads (Last 12 months)1,927
Downloads (Last 6 weeks)173

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Kelly T(2024)Zero Tolerance for BiasQueue10.1145/366464522:2(19-38)Online publication date: 29-May-2024
https://doi.org/10.1145/3664645
Kelly T(2024)Programmer Job Interviews: The Hidden AgendaQueue10.1145/363944421:6(16-26)Online publication date: 15-Jan-2024
https://doi.org/10.1145/3639444
Tarjan RZwick U(2024)Finding strong components using depth-first searchEuropean Journal of Combinatorics10.1016/j.ejc.2023.103815119(103815)Online publication date: Jun-2024
https://doi.org/10.1016/j.ejc.2023.103815
Kelly T(2020)Offline Algorithms in Low-Frequency TradingQueue10.1145/3442632.344830718:6(37-51)Online publication date: 14-Dec-2020
https://doi.org/10.1145/3442632.3448307
Kelly T(2020)Decentralized ComputingQueue10.1145/3434571.343696418:5(41-53)Online publication date: 31-Oct-2020
https://doi.org/10.1145/3434571.3436964

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Magazine Site

View this article on the magazine site (external)

Magazine Site

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Efficient k-nearest neighbors search in graph space

A General Label Search to investigate classical graph search algorithms

Decision Graph Search

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Badges

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Magazine Site

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations