{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,10,25]],"date-time":"2023-10-25T05:51:52Z","timestamp":1698213112825},"reference-count":8,"publisher":"Wiley","issue":"12","license":[{"start":{"date-parts":[[2006,10,30]],"date-time":"2006-10-30T00:00:00Z","timestamp":1162166400000},"content-version":"vor","delay-in-days":4351,"URL":"http:\/\/onlinelibrary.wiley.com\/termsAndConditions#vor"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Softw Pract Exp"],"published-print":{"date-parts":[[1994,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>In a previous article we proposed a new and efficient indexing technique that utilizes all the functors in the clause\u2010heads and the goal. The salient feature of this technique is that the selected clause\u2010head <jats:italic>unifies (modulo nonlinearity)<\/jats:italic> with the goal. As a consequence, our technique results in sharper discrimination, fewer choice points and reduced backtracking.<\/jats:p><jats:p>A na\u00efve and direct implementation of our indexing algorithms considerably slowed down the execution speeds of a wide range of programs typically seen in practice. This is because it handled deep and shallow terms, terms with few indexable arguments, small and large procedures <jats:italic>uniformly.<\/jats:italic> To beneficially extend the applicability of our algorithms we need mechanisms that are \u2018sensitive\u2019 to term structures and size and complexity of procedures. We accomplish this in the <jats:italic>v\u2010ALS<\/jats:italic> compiler by carefully decomposing our indexing process into <jats:italic>multiple stages.<\/jats:italic> The operations performed by these stages increase in complexity ranging from first argument indexing to unification (modulo nonlinearity). Further the indexing process can be terminated at any stage if it is not beneficial to continue further.<\/jats:p><jats:p>We have now completed the design and implementation of <jats:italic>v\u2010ALS.<\/jats:italic> Using it we have enhanced the performance of a broad range of programs typically encountered in practice. Our experience strongly suggests that indexing based on unification (modulo nonlinearity) is a viable idea in practice and that a broad spectrum of useful programs can realize all of its benefits.<\/jats:p>","DOI":"10.1002\/spe.4380241202","type":"journal-article","created":{"date-parts":[[2006,11,18]],"date-time":"2006-11-18T05:53:47Z","timestamp":1163829227000},"page":"1097-1119","source":"Crossref","is-referenced-by-count":3,"title":["Multistage indexing algorithms for speeding prolog execution"],"prefix":"10.1002","volume":"24","author":[{"given":"Ta Chen","family":"And","sequence":"first","affiliation":[]},{"given":"I. V.","family":"Ramakrishnan","sequence":"additional","affiliation":[]},{"given":"R.","family":"Ramesh","sequence":"additional","affiliation":[]}],"member":"311","published-online":{"date-parts":[[2006,10,30]]},"reference":[{"key":"e_1_2_1_2_2","doi-asserted-by":"crossref","unstructured":"R.Ramesh I. V.RamakrishnanandD. S.Warren \u2018Automata\u2010driven indexing of Prolog clauses\u2019 Seventeenth Annual ACM Symp. on Principles of Programming Languages San Francisco 1990 pp.281\u2013290.","DOI":"10.1145\/96709.96738"},{"key":"e_1_2_1_3_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(78)90043-0"},{"key":"e_1_2_1_4_2","doi-asserted-by":"publisher","DOI":"10.1145\/357162.357169"},{"key":"e_1_2_1_5_2","volume-title":"The Craft of Prolog","author":"O'Keefe R. A.","year":"1990"},{"issue":"3","key":"e_1_2_1_6_2","first-page":"110","article-title":"An efficient easily adaptable system for interpreting natural language queries","volume":"8","author":"Warren D. H. D.","year":"1982","journal-title":"Amer. J. Comput. Linguistics"},{"key":"e_1_2_1_7_2","doi-asserted-by":"publisher","DOI":"10.1145\/360825.360855"},{"key":"e_1_2_1_8_2","volume-title":"An abstract Prolog instruction set","author":"Warren D. H. D.","year":"1983"},{"key":"e_1_2_1_9_2","unstructured":"H.A\u00eft\u2010Kaci \u2018The WAM: A (real) tutorial\u2019 Technical Report Paris Research Laboratory Digital Equipment Corporation January1990."}],"container-title":["Software: Practice and Experience"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/api.wiley.com\/onlinelibrary\/tdm\/v1\/articles\/10.1002%2Fspe.4380241202","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/pdf\/10.1002\/spe.4380241202","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,10,24]],"date-time":"2023-10-24T05:34:56Z","timestamp":1698125696000},"score":1,"resource":{"primary":{"URL":"https:\/\/onlinelibrary.wiley.com\/doi\/10.1002\/spe.4380241202"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1994,12]]},"references-count":8,"journal-issue":{"issue":"12","published-print":{"date-parts":[[1994,12]]}},"alternative-id":["10.1002\/spe.4380241202"],"URL":"https:\/\/doi.org\/10.1002\/spe.4380241202","archive":["Portico"],"relation":{},"ISSN":["0038-0644","1097-024X"],"issn-type":[{"value":"0038-0644","type":"print"},{"value":"1097-024X","type":"electronic"}],"subject":[],"published":{"date-parts":[[1994,12]]}}}