{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,14]],"date-time":"2023-01-14T16:10:14Z","timestamp":1673712614496},"reference-count":36,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2008,8]]},"abstract":"<jats:p>\n            In this paper we propose a novel document retrieval model in which text queries are augmented with multi-dimensional taxonomy restrictions. These restrictions may be relaxed at a cost to result quality. This new model may be applicable in many arenas, including multifaceted, product, and local search, where documents are augmented with hierarchical metadata such as topic or location. We present efficient algorithms for indexing and query processing in this new retrieval model. We decompose query processing into two sub-problems: first, an online search problem to determine the correct overall level of relaxation cost that must be incurred to generate the top\n            <jats:italic>k<\/jats:italic>\n            results; and second, a budgeted relaxation search problem in which all results at a particular relaxation cost must be produced at minimal cost. We show the latter problem is solvable exactly in two hierarchical dimensions, is NP-hard in three or more dimensions, but admits efficient approximation algorithms with provable guarantees. We present experimental results evaluating our algorithms on both synthetic and real data, showing order of magnitude improvements over the baseline algorithm.\n          <\/jats:p>","DOI":"10.14778\/1453856.1453930","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"672-683","source":"Crossref","is-referenced-by-count":9,"title":["Relaxation in text search using taxonomies"],"prefix":"10.14778","volume":"1","author":[{"given":"Marcus","family":"Fontoura","sequence":"first","affiliation":[{"name":"Yahoo! Research, Sunnyvale, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vanja","family":"Josifovski","sequence":"additional","affiliation":[{"name":"Yahoo! Research, Sunnyvale, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Ravi","family":"Kumar","sequence":"additional","affiliation":[{"name":"Yahoo! Research, Sunnyvale, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Christopher","family":"Olston","sequence":"additional","affiliation":[{"name":"Yahoo! Research, Sunnyvale, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Andrew","family":"Tomkins","sequence":"additional","affiliation":[{"name":"Yahoo! Research, Sunnyvale, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Sergei","family":"Vassilvitskii","sequence":"additional","affiliation":[{"name":"Yahoo! Research, Sunnyvale, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2008,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/645482.653299"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.5555\/876875.879013"},{"key":"e_1_2_1_3_1","volume-title":"Modern Information Retrieval","author":"Baeza-Yates R.","year":"1999","unstructured":"R. Baeza-Yates and B. Ribeiro-Neto . Modern Information Retrieval . Addison Wesley , 1999 . R. Baeza-Yates and B. Ribeiro-Neto. Modern Information Retrieval. Addison Wesley, 1999."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276725"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0169-7552(98)00110-X"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/956863.956944"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/177424.178029"},{"key":"e_1_2_1_8_1","first-page":"970","volume-title":"Proc. 31st VLDB","author":"Burdick D.","year":"2005","unstructured":"D. Burdick , P. M. Deshpande , T. S. Jayram , R. Ramakrishnan , and S. Vaithyanathan . OLAP over uncertain and imprecise data . In Proc. 31st VLDB , pages 970 -- 981 , 2005 . D. Burdick, P. M. Deshpande, T. S. Jayram, R. Ramakrishnan, and S. Vaithyanathan. OLAP over uncertain and imprecise data. In Proc. 31st VLDB, pages 970--981, 2005."},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142505"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1064092.1064115"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1147\/sj.414.0697"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007588"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065191"},{"key":"e_1_2_1_14_1","first-page":"958","volume-title":"Proc. 31st VLDB","author":"Fagin R.","year":"2005","unstructured":"R. Fagin , P. Kolaitis , R. Kumar , J. Novak , D. Sivakumar , and A. Tomkins . Efficient implementation of large-scale multi-structural databases . In Proc. 31st VLDB , pages 958 -- 969 , 2005 . R. Fagin, P. Kolaitis, R. Kumar, J. Novak, D. Sivakumar, and A. Tomkins. Efficient implementation of large-scale multi-structural databases. In Proc. 31st VLDB, pages 958--969, 2005."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00026-6"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/S1389-1286(00)00069-4"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1099554.1099741"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/1316689.1316785"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(81)90111-3"},{"key":"e_1_2_1_20_1","volume-title":"Database System Implementation","author":"Garcia-Molina H.","year":"2000","unstructured":"H. Garcia-Molina , J. Ullman , and J. Widom . Database System Implementation . Prentice Hall , 2000 . H. Garcia-Molina, J. Ullman, and J. Widom. Database System Implementation. Prentice Hall, 2000."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009726021843"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1147\/sj.431.0064"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1002\/asi.10268"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.5555\/1315451.1315524"},{"key":"e_1_2_1_25_1","first-page":"530","volume-title":"Proc. 25th VLDB","author":"Jagadish H. V.","year":"1999","unstructured":"H. V. Jagadish , L. S. Lakshmanan , and D. Srivastava . What can hierarchies do for data warehouses ? In Proc. 25th VLDB , pages 530 -- 541 , 1999 . H. V. Jagadish, L. S. Lakshmanan, and D. Srivastava. What can hierarchies do for data warehouses? In Proc. 25th VLDB, pages 530--541, 1999."},{"key":"e_1_2_1_26_1","first-page":"505","volume-title":"Proc. 31st VLDB","author":"Kacholia V.","year":"2005","unstructured":"V. Kacholia , S. Pandit , S. Chakrabarti , S. Sudarshan , R. Desai , and H. Karambelkar . Bidirectional expansion for keyword search on graph databases . In Proc. 31st VLDB , pages 505 -- 516 , 2005 . V. Kacholia, S. Pandit, S. Chakrabarti, S. Sudarshan, R. Desai, and H. Karambelkar. Bidirectional expansion for keyword search on graph databases. In Proc. 31st VLDB, pages 505--516, 2005."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142591"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/1005332.1005345"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/1315451.1315464"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/371920.372095"},{"key":"e_1_2_1_31_1","volume-title":"The pagerank citation ranking: Bringing order to the web. Technical report","author":"Page L.","year":"1998","unstructured":"L. Page , S. Brin , R. Motwani , and T. Winograd . The pagerank citation ranking: Bringing order to the web. Technical report , Stanford Digital Library Technologies Project , 1998 . L. Page, S. Brin, R. Motwani, and T. Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford Digital Library Technologies Project, 1998."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1016\/0306-4573(95)00020-H"},{"key":"e_1_2_1_33_1","volume-title":"Morgan Kaufmann","author":"Witten I.","year":"1999","unstructured":"I. Witten , A. Moffat , and T. Bell . Managing Gigabytes . Morgan Kaufmann , 1999 . I. Witten, A. Moffat, and T. Bell. Managing Gigabytes. Morgan Kaufmann, 1999."},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066217"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/642611.642681"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247541"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1453856.1453930","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:10:50Z","timestamp":1672225850000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1453856.1453930"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2008,8]]},"references-count":36,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2008,8]]}},"alternative-id":["10.14778\/1453856.1453930"],"URL":"https:\/\/doi.org\/10.14778\/1453856.1453930","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2008,8]]}}}