Abstract
We study the problem of navigating through a database of similar objects using comparisons under heterogeneous demand, a problem closely related to small-world network design. We show that, under heterogeneous demand, the small-world network design problem is NP-hard. Given the above negative result, we propose a novel mechanism for small-world network design and provide an upper bound on its performance under heterogeneous demand. The above mechanism has a natural equivalent in the context of content search through comparisons, again under heterogeneous demand; we use this to establish both upper and lower bounds on content search through comparisons.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Clarkson, K.L.: Nearest-neighbor searching and metric space dimensions. In: Shakhnarovich, G., Darrell, T., Indyk, P. (eds.) Nearest-Neighbor Methods for Learning and Vision: Theory and Practice, pp. 15–59. MIT Press, G. Shakhnarovich (2006)
Cover, T.M., Thomas, J.: Elements of Information Theory. Wiley, Chichester (1991)
Fraigniaud, P., Giakkoupis, G.: On the searchability of small-world networks with arbitrary underlying structure. In: STOC (2010)
Fraigniaud, P., Lebhar, E., Lotker, Z.: A doubling dimension threshold θ(loglogn) for augmented graph navigability. In: Azar, Y., Erlebach, T. (eds.) ESA 2006. LNCS, vol. 4168, pp. 376–386. Springer, Heidelberg (2006)
Goyal, N., Lifshits, Y., Schutze, H.: Disorder inequality: a combinatorial approach to nearest neighbor search. In: WSDM (2008)
Indyk, P., Motwani, R.: Approximate nearest neighbors: Towards removing the curse of dimensionality. In: STOC, pp. 604–613 (1998)
Karbasi, A., Ioannidis, S., Massoulie, L.: Content search through comparisons. Tech. Rep. CR-PRL-2010-07-0002, Technicolor (2010)
Karger, D., Ruhl, M.: Finding nearest neighbors in growth-restricted metrics. In: SODA (2002)
Kleinberg, J.: The small-world phenomenon: An algorithmic perspective. In: STOC (2000)
Krauthgamer, R., Lee, J.R.: Navigating nets: simple algorithms for proximity search. In: SODA (2004)
Lifshits, Y., Zhang, S.: Combinatorial algorithms for nearest neighbors, near-duplicates and small-world design. In: SODA (2009)
Tschopp, D., Diggavi, S.N.: Approximate nearest neighbor search through comparisons (2009)
Tschopp, D., Diggavi, S.N.: Facebrowsing: Search and navigation through comparisons. In: ITA Workshop (2010)
White, R., Roth, R.: Exploratory Search: Beyond the Query-Response Paradigm. Morgan & Claypool (2009)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2011 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Karbasi, A., Ioannidis, S., Massoulié, L. (2011). Content Search through Comparisons. In: Aceto, L., Henzinger, M., Sgall, J. (eds) Automata, Languages and Programming. ICALP 2011. Lecture Notes in Computer Science, vol 6756. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-22012-8_48
Download citation
DOI: https://doi.org/10.1007/978-3-642-22012-8_48
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-22011-1
Online ISBN: 978-3-642-22012-8
eBook Packages: Computer ScienceComputer Science (R0)