Combinatorial algorithms for nearest neighbors, near-duplicates and small-world design

ABSTRACT

We study the so called combinatorial framework for algorithmic problems in similarity spaces. Namely, the input dataset is represented by a comparison oracle that given three points x, y, y' answers whether y or y' is closer to x. We assume that the similarity order of the dataset satisfies the four variations of the following disorder inequality: if x is the a'th most similar object to y and y is the b'th most similar object to z, then x is among the D(a + b) most similar objects to z, where D is a relatively small disorder constant.

Though the oracle gives much less information compared to the standard general metric space model where distance values are given, one can still design very efficient algorithms for various fundamental computational tasks. For nearest neighbor search we present deterministic and exact algorithm with almost linear time and space complexity of preprocessing, and near-logarithmic time complexity of search. Then, for near-duplicate detection we present the first known deterministic algorithm that requires just near-linear time + time proportional to the size of output. Finally, we show that for any dataset satisfying the disorder inequality a visibility graph can be constructed: all outdegrees are near-logarithmic and greedy routing deterministically converges to the nearest neighbor of a target in logarithmic number of steps. The later result is the first known work-around for Navarro's impossibility of generalizing Delaunay graphs.

The technical contribution of the paper consists of handling "false positives" in data structures and an algorithmic technique up-aside-down-filter.

REFERENCES

• 1: Ittai Abraham , Cyril Gavoille , Andrew V. Goldberg , Dahlia Malkhi, Routing in Networks with Low Doubling Dimension, Proceedings of the 26th IEEE International Conference on Distributed Computing Systems, p.75, July 04-07, 2006 [doi>10.1109/ICDCS.2006.72]
• 2: Sunil Arya , David M. Mount, Approximate nearest neighbor queries in fixed dimensions, Proceedings of the fourth annual ACM-SIAM Symposium on Discrete algorithms, p.271-280, January 25-27, 1993, Austin, Texas, United States
• 3: Maria-Florina Balcan , Avrim Blum , Santosh Vempala, A discriminative framework for clustering via similarity functions, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374474]
• 4: Ziv Bar-Yossef , Idit Keidar , Uri Schonfeld, Do not crawl in the dust: different urls with similar text, Proceedings of the 16th international conference on World Wide Web, May 08-12, 2007, Banff, Alberta, Canada [doi>10.1145/1242572.1242588]
• 5: Alina Beygelzimer , Sham Kakade , John Langford, Cover trees for nearest neighbor, Proceedings of the 23rd international conference on Machine learning, p.97-104, June 25-29, 2006, Pittsburgh, Pennsylvania [doi>10.1145/1143844.1143857]
• 6: Andrei Z. Broder , Steven C. Glassman , Mark S. Manasse , Geoffrey Zweig, Syntactic clustering of the Web, Selected papers from the sixth international conference on World Wide Web, p.1157-1166, September 1997, Santa Clara, California, United States
• 7: Andrei Z. Broder , Moses Charikar , Alan M. Frieze , Michael Mitzenmacher, Min-wise independent permutations (extended abstract), Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.327-336, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276781]
• 8: Kaushik Chakrabarti , Eamonn Keogh , Sharad Mehrotra , Michael Pazzani, Locally adaptive dimensionality reduction for indexing large time series databases, ACM Transactions on Database Systems (TODS), v.27 n.2, p.188-228, June 2002 [doi>10.1145/568518.568520]
• 9: T.-H. Hubert Chan , Michael Dinitz , Anupam Gupta, Spanners with slack, Proceedings of the 14th conference on Annual European Symposium, p.196-207, September 11-13, 2006, Zurich, Switzerland [doi>10.1007/11841036_20]
• 10: Moses S. Charikar, Similarity estimation techniques from rounding algorithms, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509965]
• 11: Moses Charikar , Konstantin Makarychev , Yury Makarychev, A divide and conquer algorithm for d-dimensional arrangement, Proceedings of the eighteenth annual ACM-SIAM symposium on Discrete algorithms, p.541-546, January 07-09, 2007, New Orleans, Louisiana
• 12: K. L. Clarkson. Nearest neighbor queries in metric spaces. Discrete and Computational Geometry, 1999.
• 13: K. L. Clarkson. Nearest-neighbor searching and metric space dimensions. In Nearest-Neighbor Methods for Learning and Vision: Theory and Practice, MIT Press, 2006.
• 14: Richard Cole , Lee-Ad Gottlieb, Searching dynamic point sets in spaces with bounded doubling dimension, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132599]
• 15: Antonio Corral , Yannis Manolopoulos , Yannis Theodoridis , Michael Vassilakopoulos, Closest pair queries in spatial databases, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.189-200, May 15-18, 2000, Dallas, Texas, United States
• 16: Pierre Fraigniaud , Emmanuelle Lebhar , Zvi Lotker, A doubling dimension threshold θ(loglogn) for augmented graph navigability, Proceedings of the 14th conference on Annual European Symposium, p.376-386, September 11-13, 2006, Zurich, Switzerland [doi>10.1007/11841036_35]
• 17: Navin Goyal , Yury Lifshits , Hinrich Schütze, Disorder inequality: a combinatorial approach to nearest neighbor search, Proceedings of the international conference on Web search and web data mining, February 11-12, 2008, Palo Alto, California, USA [doi>10.1145/1341531.1341538]
• 18: Sariel Har-Peled , Manor Mendel, Fast Construction of Nets in Low-Dimensional Metrics and Their Applications, SIAM Journal on Computing, v.35 n.5, p.1148-1184, 2006 [doi>10.1137/S0097539704446281]
• 19: Kirsten Hildrum , John Kubiatowicz , Sean Ma , Satish Rao, A note on the nearest neighbor in growth-restricted metrics, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 20: Piotr Indyk , Rajeev Motwani, Approximate nearest neighbors: towards removing the curse of dimensionality, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.604-613, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276876]
• 21: David R. Karger , Matthias Ruhl, Finding nearest neighbors in growth-restricted metrics, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.510013]
• 22: Jon Kleinberg, The small-world phenomenon: an algorithm perspective, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.163-170, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335325]
• 23: Aleksander Kołcz , Abdur Chowdhury , Joshua Alspector, Improved robustness of signature-based near-replica detection via lexicon randomization, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014127]
• 24: Robert Krauthgamer , James R. Lee, The black-box complexity of nearest-neighbor search, Theoretical Computer Science, v.348 n.2, p.262-276, 8 December 2005 [doi>10.1016/j.tcs.2005.09.017]
• 25: Robert Krauthgamer , James R. Lee, Navigating nets: simple algorithms for proximity search, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 26: Eyal Kushilevitz , Rafail Ostrovsky , Yuval Rabani, Efficient search for approximate nearest neighbor in high dimensional spaces, Proceedings of the thirtieth annual ACM symposium on Theory of computing, p.614-623, May 24-26, 1998, Dallas, Texas, United States [doi>10.1145/276698.276877]
• 27: Y. Lifshits and D. Nowotka. Estimation of the click volume by large scale regression analysis. In CSR'07.
• 28: R. Macíyas and C. Segovia. Lipschitz functions on spaces of homogeneous type. Advances in Mathematics, 1979.
• 29: Gonzalo Navarro, Searching in metric spaces by spatial approximation, The VLDB Journal — The International Journal on Very Large Data Bases, v.11 n.1, p.28-46, August 2002 [doi>10.1007/s007780200060]
• 30: M. E. J. Newman. Detecting community structure in networks. The European Physical Journal B-Condensed Matter, 2004.
• 31: C. G. Plaxton, R. Rajaraman, and A. W. Richa. Accessing nearby copies of replicated objects in a distributed environment. Theory Comput. Syst., 1999.
• 32: Aleksandrs Slivkins, Distance estimation and object location via rings of neighbors, Proceedings of the twenty-fourth annual ACM symposium on Principles of distributed computing, July 17-20, 2005, Las Vegas, NV, USA [doi>10.1145/1073814.1073823]
• 33: Bernard Wong , Aleksandrs Slivkins , Emin Gün Sirer, Meridian: a lightweight network location service without virtual coordinates, Proceedings of the 2005 conference on Applications, technologies, architectures, and protocols for computer communications, August 22-26, 2005, Philadelphia, Pennsylvania, USA
• 34: Pavel Zezula , Giuseppe Amato , Vlastislav Dohnal , Michal Batko, Similarity Search: The Metric Space Approach (Advances in Database Systems), Springer-Verlag New York, Inc., Secaucus, NJ, 2005

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.0 General