{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,21]],"date-time":"2025-05-21T06:12:51Z","timestamp":1747807971925},"reference-count":34,"publisher":"Association for Computing Machinery (ACM)","issue":"1-2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2010,9]]},"abstract":"\n Keyword search in relational databases has been extensively studied. Given a relational database, a keyword query finds a set of interconnected tuple structures connected by foreign key references. On rdbms, a keyword query is processed in two steps, namely, candidate networks (\n CN<\/jats:italic>\n s) generation and\n CN<\/jats:italic>\n s evaluation, where a\n CN<\/jats:italic>\n is an sql. In common, a keyword query needs to be processed using over 10,000 sqls. There are several approaches to process a keyword query on rdbms, but there is a limit to achieve high performance on a uniprocessor architecture. In this paper, we study parallel computing keyword queries on a multicore architecture. We give three observations on keyword query computing, namely, a large number of sqls that needs to be processed, high sharing possibility among sqls, and large intermediate results with small number of final results. All make it challenging for parallel keyword queries computing. We investigate three approaches. We first study the query level parallelism, where each sql is processed by one core. We distribute the sqls into different cores based on three objectives, regarding minimizing workload skew, minimizing intercore sharing and maximizing intra-core sharing respectively. Such an approach has the potential risk of load unbalancing through accumulating errors of cost estimation. We then study the operation level parallelism, where each operation of an sql is processed by one core. All operations are processed in stages, where in each stage the costs of operations are re-estimated to reduce the accumulated error. Such operation level parallelism still has drawbacks of workload skew when large operations are involved and a large number of cores are used. Finally, we propose a new algorithm that partitions relations adaptively in order to minimize the extra cost of partitioning and at the same time reduce workload skew. We conducted extensive performance studies using two large real datasets,\n DBLP<\/jats:italic>\n and\n IMDB<\/jats:italic>\n , and we report the efficiency of our approaches in this paper.\n <\/jats:p>","DOI":"10.14778\/1920841.1920854","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"58-69","source":"Crossref","is-referenced-by-count":10,"title":["Ten thousand SQLs"],"prefix":"10.14778","volume":"3","author":[{"given":"Lu","family":"Qin","sequence":"first","affiliation":[{"name":"The Chinese University of Hong Kong"}]},{"given":"Jeffrey Xu","family":"Yu","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong"}]},{"given":"Lijun","family":"Chang","sequence":"additional","affiliation":[{"name":"The Chinese University of Hong Kong"}]}],"member":"320","published-online":{"date-parts":[[2010,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/876875.879013"},{"key":"e_1_2_1_2_1","volume-title":"Proc. of VLDB'04","author":"Balmin A.","year":"2004"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.5555\/876875.879034"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2008.260"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275492"},{"key":"e_1_2_1_6_1","doi-asserted-by":"crossref","unstructured":"B. B. Dalvi M. Kshirsagar and S. Sudarshan. Keyword search on external memory data graphs. PVLDB 1(1) 2008. B. B. Dalvi M. Kshirsagar and S. Sudarshan. Keyword search on external memory data graphs. PVLDB 1(1) 2008.","DOI":"10.14778\/1453856.1453982"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.367929"},{"key":"e_1_2_1_8_1","volume-title":"Networks","author":"Dreyfus S. E.","year":"1972"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376708"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/152610.152611"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247516"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/1315451.1315524"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/1331904.1331905"},{"key":"e_1_2_1_14_1","volume-title":"Proc. of VLDB'02","author":"Hristidis V.","year":"2002"},{"key":"e_1_2_1_15_1","volume-title":"Proc. of VLDB'05","author":"Kacholia V.","year":"2005"},{"key":"e_1_2_1_16_1","doi-asserted-by":"crossref","unstructured":"A. Kementsietsidis F. Neven D. V. de Craen and S. Vansummeren. Scalable multi-query optimization for exploratory queries over federated scientific databases. PVLDB 1(1) 2008. A. Kementsietsidis F. Neven D. V. de Craen and S. Vansummeren. Scalable multi-query optimization for exploratory queries over federated scientific databases. PVLDB 1(1) 2008.","DOI":"10.14778\/1453856.1453864"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142351.1142377"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1376616.1376706"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142536"},{"key":"e_1_2_1_20_1","volume-title":"IEEE Computer Society Press","author":"Lu H.","year":"1994"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247495"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247548"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/128762.128764"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.42"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559845.1559917"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.67"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.200"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335419"},{"key":"e_1_2_1_29_1","doi-asserted-by":"crossref","unstructured":"S. Tatikonda and S. Parthasarathy. Mining tree-structured data on multicore systems. PVLDB 2(1):694--705 2009. S. Tatikonda and S. Parthasarathy. Mining tree-structured data on multicore systems. PVLDB 2(1):694--705 2009.","DOI":"10.14778\/1687627.1687706"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICPP.2007.49"},{"key":"e_1_2_1_31_1","volume-title":"Morgan Kaufmann","author":"Yu C.","year":"1998"},{"key":"e_1_2_1_32_1","volume-title":"Morgan and Claypool Publishers","author":"Yu J. X.","year":"2010"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3872.3874"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247540"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1920841.1920854","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T11:43:12Z","timestamp":1672227792000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1920841.1920854"}},"subtitle":["parallel keyword queries computing"],"short-title":[],"issued":{"date-parts":[[2010,9]]},"references-count":34,"journal-issue":{"issue":"1-2","published-print":{"date-parts":[[2010,9]]}},"alternative-id":["10.14778\/1920841.1920854"],"URL":"https:\/\/doi.org\/10.14778\/1920841.1920854","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2010,9]]}}}