{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,3,2]],"date-time":"2024-03-02T09:17:48Z","timestamp":1709371068171},"reference-count":20,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2008,10,30]],"date-time":"2008-10-30T00:00:00Z","timestamp":1225324800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Theory Comput Syst"],"published-print":{"date-parts":[[2010,1]]},"DOI":"10.1007\/s00224-008-9154-6","type":"journal-article","created":{"date-parts":[[2008,10,29]],"date-time":"2008-10-29T20:34:52Z","timestamp":1225312492000},"page":"104-119","source":"Crossref","is-referenced-by-count":4,"title":["Maximal Intersection Queries in Randomized Input Models"],"prefix":"10.1007","volume":"46","author":[{"given":"Benjamin","family":"Hoffmann","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mikhail","family":"Lifshits","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yury","family":"Lifshits","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Dirk","family":"Nowotka","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2008,10,30]]},"reference":[{"issue":"3","key":"9154_CR1","doi-asserted-by":"crossref","first-page":"322","DOI":"10.1145\/502807.502809","volume":"33","author":"C. B\u00f6hm","year":"2001","unstructured":"B\u00f6hm, C., Berchtold, S., Keim, D.A.: Searching in high-dimensional spaces: Index structures for improving the performance of multimedia databases. ACM Comput. Surv. 33(3), 322\u2013373 (2001)","journal-title":"ACM Comput. Surv."},{"key":"9154_CR2","first-page":"21","volume-title":"SEQUENCES \u201997: Proceedings of the Compression and Complexity of Sequences 1997","author":"A. Broder","year":"1997","unstructured":"Broder, A.: On the resemblance and containment of documents. In: SEQUENCES \u201997: Proceedings of the Compression and Complexity of Sequences 1997, Washington, DC, USA, p. 21. IEEE Comput. Soc., Los Alamitos (1997)"},{"issue":"2","key":"9154_CR3","doi-asserted-by":"crossref","first-page":"381","DOI":"10.1109\/18.52484","volume":"36","author":"J. Bruck","year":"1990","unstructured":"Bruck, J., Naor, M.: The hardness of decoding linear codes with preprocessing. IEEE Trans. Inf. Theory 36(2), 381\u2013385 (1990)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"3","key":"9154_CR4","doi-asserted-by":"crossref","first-page":"273","DOI":"10.1145\/502807.502808","volume":"33","author":"E. Ch\u00e1vez","year":"2001","unstructured":"Ch\u00e1vez, E., Navarro, G., Baeza-Yates, R., Marroqu\u00edn, J.L.: Searching in metric spaces. ACM Comput. Surv. 33(3), 273\u2013321 (2001)","journal-title":"ACM Comput. Surv."},{"key":"9154_CR5","volume-title":"Nearest-Neighbor Methods for Learning and Vision: Theory and Practice","author":"K. Clarkson","year":"2006","unstructured":"Clarkson, K.: Nearest-neighbor searching and metric space dimensions. In: Nearest-Neighbor Methods for Learning and Vision: Theory and Practice. MIT Press, Cambridge (2006)"},{"key":"9154_CR6","doi-asserted-by":"crossref","first-page":"91","DOI":"10.1145\/1007352.1007374","volume-title":"STOC \u201904: Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing","author":"R. Cole","year":"2004","unstructured":"Cole, R., Gottlieb, L.-A., Lewenstein, M.: Dictionary matching and indexing with errors and don\u2019t cares. In: STOC \u201904: Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing, New York, NY, USA, pp. 91\u2013100. Assoc. Comput. Mach., New York (2004)"},{"key":"9154_CR7","doi-asserted-by":"crossref","first-page":"301","DOI":"10.1145\/872757.872795","volume-title":"SIGMOD \u201903: Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data","author":"R. Fagin","year":"2003","unstructured":"Fagin, R., Kumar, R., Sivakumar, D.: Efficient similarity search and classification via rank aggregation. In: SIGMOD \u201903: Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, New York, NY, USA, pp. 301\u2013312. Assoc. Comput. Mach., New York (2003)"},{"key":"9154_CR8","doi-asserted-by":"crossref","unstructured":"Goyal, N., Lifshits, Y., Sch\u00fctze, H.: Disorder inequality: a combinatorial approach to nearest neighbor search. In: WSDM, pp. 25\u201332 (2008)","DOI":"10.1145\/1341531.1341538"},{"issue":"4","key":"9154_CR9","doi-asserted-by":"crossref","first-page":"517","DOI":"10.1145\/958942.958948","volume":"28","author":"G.R. Hjaltason","year":"2003","unstructured":"Hjaltason, G.R., Samet, H.: Index-driven similarity search in metric spaces (survey article). ACM Trans. Database Syst. 28(4), 517\u2013580 (2003)","journal-title":"ACM Trans. Database Syst."},{"key":"9154_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"227","DOI":"10.1007\/978-3-540-74510-5_24","volume-title":"CSR","author":"B. Hoffmann","year":"2007","unstructured":"Hoffmann, B., Lifshits, Y., Nowotka, D.: Maximal intersection queries in randomized graph models. In: Diekert, V., Volkov, M.V., Voronkov, A. (eds.) CSR. Lecture Notes in Computer Science, vol. 4649, pp. 227\u2013236. Springer, Berlin (2007)"},{"key":"9154_CR11","volume-title":"Handbook of Discrete and Computational Geometry","author":"P. Indyk","year":"2004","unstructured":"Indyk, P.: Nearest neighbors in high-dimensional spaces. In: Goodman, J.E., O\u2019Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, 2nd edn. CRC Press, Boca Raton (2004). Chap. 39","edition":"2"},{"key":"9154_CR12","doi-asserted-by":"crossref","first-page":"741","DOI":"10.1145\/509907.510013","volume-title":"STOC \u201902: Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing","author":"D.R. Karger","year":"2002","unstructured":"Karger, D.R., Ruhl, M.: Finding nearest neighbors in growth-restricted metrics. In: STOC \u201902: Proceedings of the Thirty-Fourth Annual ACM Symposium on Theory of Computing, New York, NY, USA, pp. 741\u2013750. Assoc. Comput. Mach., New York (2002)"},{"key":"9154_CR13","doi-asserted-by":"crossref","first-page":"599","DOI":"10.1145\/258533.258653","volume-title":"STOC \u201997: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing","author":"J.M. Kleinberg","year":"1997","unstructured":"Kleinberg, J.M.: Two algorithms for nearest-neighbor search in high dimensions. In: STOC \u201997: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, New York, NY, USA, pp. 599\u2013608. Assoc. Comput. Mach., New York (1997)"},{"key":"9154_CR14","first-page":"798","volume-title":"SODA \u201904: Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms","author":"R. Krauthgamer","year":"2004","unstructured":"Krauthgamer, R., Lee, J.R.: Navigating nets: simple algorithms for proximity search. In: SODA \u201904: Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, Philadelphia, PA, USA, pp. 798\u2013807. SIAM, Philadelphia (2004)"},{"key":"9154_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"216","DOI":"10.1007\/978-3-540-74510-5_23","volume-title":"CSR","author":"Y. Lifshits","year":"2007","unstructured":"Lifshits, Y., Nowotka, D.: Estimation of the click volume by large scale regression analysis. In: Diekert, V., Volkov, M.V., Voronkov, A. (eds.) CSR. Lecture Notes in Computer Science, vol. 4649, pp.\u00a0216\u2013226. Springer, Berlin (2007)"},{"issue":"5","key":"9154_CR16","doi-asserted-by":"crossref","first-page":"185","DOI":"10.1016\/j.ipl.2005.08.001","volume":"96","author":"M.G. Maa\u00df","year":"2005","unstructured":"Maa\u00df, M.G., Nowak, J.: A new method for approximate indexing and dictionarylookup with one error. Inf. Process. Lett. 96(5), 185\u2013191 (2005)","journal-title":"Inf. Process. Lett."},{"key":"9154_CR17","volume-title":"Foundations of Statistical Natural Language Processing","author":"C.D. Manning","year":"1999","unstructured":"Manning, C.D., Sch\u00fctze, H.: Foundations of Statistical Natural Language Processing. MIT Press, Cambridge (1999)"},{"key":"9154_CR18","doi-asserted-by":"crossref","first-page":"167","DOI":"10.1137\/S003614450342480","volume":"45","author":"M.E.J. Newman","year":"2003","unstructured":"Newman, M.E.J.: The structure and function of complex networks. SIAM Rev. 45, 167 (2003)","journal-title":"SIAM Rev."},{"key":"9154_CR19","doi-asserted-by":"crossref","DOI":"10.1007\/0-387-29151-2","volume-title":"Similarity Search\u2014The Metric Space Approach","author":"P. Zezula","year":"2006","unstructured":"Zezula, P., Amato, G., Dohnal, V., Batko, M.: Similarity Search\u2014The Metric Space Approach, vol.\u00a032. Springer, Berlin (2006)"},{"issue":"2","key":"9154_CR20","doi-asserted-by":"crossref","first-page":"6","DOI":"10.1145\/1132956.1132959","volume":"38","author":"J. Zobel","year":"2006","unstructured":"Zobel, J., Moffat, A.: Inverted files for text search engines. ACM Comput. Surv. 38(2), 6 (2006)","journal-title":"ACM Comput. Surv."}],"container-title":["Theory of Computing Systems"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-008-9154-6.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00224-008-9154-6\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00224-008-9154-6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,5,9]],"date-time":"2020-05-09T19:33:57Z","timestamp":1589052837000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00224-008-9154-6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,10,30]]},"references-count":20,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["9154"],"URL":"https:\/\/doi.org\/10.1007\/s00224-008-9154-6","relation":{},"ISSN":["1432-4350","1433-0490"],"issn-type":[{"value":"1432-4350","type":"print"},{"value":"1433-0490","type":"electronic"}],"subject":[],"published":{"date-parts":[[2008,10,30]]}}}