Search

It is now well understood that social media plays an increasingly important role in consumers' decision making. However, an overload of social media content in product search engines can hinder consumers from efficiently seeking information. We propose a structural econometric model to understand consumers' preferences and costs on search engines to improve user experience under unstructured social media. Our model combines an optimal stopping framework with an individual-level random utility choice model and analyzes click behavior in conjunction with purchase choices. Our model accounts for three major constraints in a consumer's decision-making process: (1) interdependency in decision making for different alternatives, (2) sequential arrival of information revealed by click-throughs, and (3) nonnegligible search cost. Our approach allows us to jointly estimate consumers' heterogeneous preferences and search costs under the interplay of social media and search engines, and to predict search and purchase behavior for each consumer. We validate the model using an individual session-level data set of approximately seven million observations resulting in room bookings in 2,117 U.S. hotels. Interestingly, our analysis allows us to quantify the trade-off between consumers' benefits and cognitive costs from using large-scale unstructured social media information during decision making. Our policy experiments show that providing a carefully curated digest of social media content during the earlier stages of consumer search (i.e., on the search results summary page) can lead to a 12.01% increase in the overall search engine revenue. History: Accepted by Anandhi Bharadwaj, information systems. Supplemental Material: The online appendix is available at https://doi.org/10.1287/mnsc.2017.2991. Keywords: consumer search * search cost * search engines * structural modeling * social media, 1. Introduction With the growing pervasiveness of social media, the volume and complexity of information product search engines need to access from their own platforms has been increasing rapidly. For [...]

A large amount of structured information is buried in unstructured text. Information extraction systems can extract structured relations from the documents and enable sophisticated, SQL-like queries over unstructured text. Information extraction systems are not perfect and their output has imperfect precision and recall (i.e., contains spurious tuples and misses good tuples). Typically, an extraction system has a set of parameters that can be used as "knobs" to tune the system to be either precision- or recall-oriented. Furthermore, the choice of documents processed by the extraction system also affects the quality of the extracted relation. So far, estimating the output quality of an information extraction task has been an ad hoc procedure, based mainly on heuristics. In this article, we show how to use Receiver Operating Characteristic (ROC) curves to estimate the extraction quality in a statistically robust way and show how to use ROC analysis to select the extraction parameters in a principled manner. Furthermore, we present analytic models that reveal how different document retrieval strategies affect the quality of the extracted relation. Finally, we present our maximum likelihood approach for estimating, on the fly, the parameters required by our analytic models to predict the runtime and the output quality of each execution plan. Our experimental evaluation demonstrates that our optimization approach predicts accurately the output quality and selects the fastest execution plan that satisfies the output quality restrictions. Categories and Subject Descriptors: H.2.4 [Database Management]: Systems--Textual databases; distributed databases General Terms: Algorithms, Experimentation, Measurement, Performance Additional Key Words and Phrases: Information Extraction, ROC curves

Many valuable text databases on the web have noncrawlable contents that are "hidden" behind search interfaces. Metasearchers are helpful tools for searching over multiple such "hidden-web" text databases at once through a unified query interface. An important step in the metasearching process is database selection, or determining which databases are the most relevant for a given user query. The state-of-the-art database selection techniques rely on statistical summaries of the database contents, generally including the database vocabulary and associated word frequencies. Unfortunately, hidden-web text databases typically do not export such summaries, so previous research has developed algorithms for constructing approximate content summaries from document samples extracted from the databases via querying. We present a novel "focused-probing" sampling algorithm that detects the topics covered in a database and adaptively extracts documents that are representative of the topic coverage of the database. Our algorithm is the first to construct content summaries that include the frequencies of the words in the database. Unfortunately, Zipf's law practically guarantees that for any relatively large database, content summaries built from moderately sized document samples will fail to cover many low-frequency words; in turn, incomplete content summaries might negatively affect the database selection process, especially for short queries with infrequent words. To enhance the sparse document samples and improve the database selection decisions, we exploit the fact that topically similar databases tend to have similar vocabularies, so samples extracted from databases with a similar topical focus can complement each other. We have developed two database selection algorithms that exploit this observation. The first algorithm proceeds hierarchically and selects the best categories for a query, and then sends the query to the appropriate databases in the chosen categories. The second algorithm uses "shrinkage," a statistical technique for improving parameter estimation in the face of sparse data, to enhance the database content summaries with category-specific words. We describe how to modify existing database selection algorithms to adaptively decide (at runtime) whether shrinkage is beneficial for a query. A thorough evaluation over a variety of databases, including 315 real web databases as well as TREC data, suggests that the proposed sampling methods generate high-quality content summaries and that the database selection algorithms produce significantly more relevant database selection decisions and overall search results than existing algorithms. Categories and Subject Descriptors: H.3.1 [Information Storage and Retrieval]: Content Analysis and Indexing--Abstracting methods, indexing methods; H.3.3 [Information Storage and Retrieval]: Information Search and Retrieval--Search process, selection process; H.3.4 [Information Storage and Retrieval]: Systems and Software Information networks, performance evaluation (efficiency and effectiveness); H.3.5 [Information Storage and Retrieval]: Online Information Services--Web-based services; H.3.6 [Information Storage and Retrieval]: Library Automation--Large text archives; H.3.7 [Information Storage and Retrieval]: Digital Libraries; H.2.4 [Database Management]: Systems--Textual databases, distributed databases; H.2.5 [Database Management]: Heterogeneous Databases General Terms: Algorithms, Experimentation, Measurement, Performance Additional Key Words and Phrases: Distributed information retrieval, web search, database selection

Text is ubiquitous and, not surprisingly, many important applications rely on textual data for a variety of tasks. As a notable example, information extraction applications derive structured relations from unstructured text; as another example, focused crawlers explore the Web to locate pages about specific topics. Execution plans for text-centric tasks follow two general paradigms for processing a text database: either we can scan, or "crawl," the text database or, alternatively, we can exploit search engine indexes and retrieve the documents of interest via carefully crafted queries constructed in task-specific ways. The choice between crawl- and query-based execution plans can have a substantial impact on both execution time and output "completeness" (e.g., in terms of recall). Nevertheless, this choice is typically ad hoc and based on heuristics or plain intuition. In this article, we present fundamental building blocks to make the choice of execution plans for text-centric tasks in an informed, cost-based way. Towards this goal, we show how to analyze query- and crawl-based plans in terms of both execution time and output completeness. We adapt results from random-graph theory and statistics to develop a rigorous cost model for the execution plans. Our cost model reflects the fact that the performance of the plans depends on fundamental task-specific properties of the underlying text databases. We identify these properties and present efficient techniques for estimating the associated parameters of the cost model. We also present two optimization approaches for text-centric tasks that rely on the cost-model parameters and select efficient execution plans. Overall, our optimization approaches help build efficient execution plans for a task, resulting in significant efficiency and output completeness benefits. We complement our results with a large-scale experimental evaluation for three important text-centric tasks and over multiple real-life data sets. Categories and Subject Descriptors: H.2.4 [Database Management]: Systems--Textual databases, distributed databases General Terms: Algorithms, Experimentation, Measurement, Performance Additional Key Words and Phrases: Metasearching, text database selection, distributed information retrieval, information extraction, focused crawling

Large amounts of (often valuable) information are stored in web-accessible text databases. "Metasearchers" provide unified interfaces to query multiple such databases at once. For efficiency, metasearchers rely on succinct statistical summaries of the database contents to select the best databases for each query. So far, database selection research has largely assumed that databases are static, so the associated statistical summaries do not evolve over time. However, databases are rarely static and the statistical summaries that describe their contents need to be updated periodically to reflect content changes. In this article, we first report the results of a study showing how the content summaries of 152 real web databases evolved over a period of 52 weeks. Then, we show how to use "survival analysis" techniques in general, and Cox's proportional hazards regression in particular, to model database changes over time and predict when we should update each content summary. Finally, we exploit our change model to devise update schedules that keep the summaries up to date by contacting databases only when needed, and then we evaluate the quality of our schedules experimentally over real web databases. Categories and Subject Descriptors: H.2.4 [Database Management]: Systems--Textual databases, Distributed databases; H.2.5 [Database Management]: Heterogeneous Databases; H.3.1 [Information Storage and Retrieval]: Content Analysis and Indexing--Abstracting methods, Indexing methods; H.3.3 [Information Storage and Retrieval]: Information Search and Retrieval--Clustering, Information filtering, Search process, Selection process; H.3.4 [Information Storage and Retrieval]: Systems and Software--Information networks, Performance evaluation (efficiency and effectiveness); H.3.5 [Information Storage and Retrieval]: Online Information Services--Web-based services; H.3.6 [Information Storage and Retrieval]: Library Automation--Large text archives; H.3.7 [Information Storage and Retrieval]: Digital Libraries General Terms: Algorithms, Experimentation, Measurement, Performance Additional Key Words and Phrases: Metasearching, text database selection, distributed information retrieval

Often, in the real world, entities have two or more representations in databases. Duplicate records do not share a common key and/or they contain errors that make duplicate matching a difficult task. Errors are introduced as the result of transcription errors, incomplete information, lack of standard formats, or any combination of these factors. In this paper, we present a thorough analysis of the literature on duplicate record detection. We cover similarity metrics that are commonly used to detect similar field entries, and we present an extensive set of duplicate detection algorithms that can detect approximately duplicate records in a database. We also cover multiple techniques for improving the efficiency and scalability of approximate duplicate detection algorithms. We conclude with coverage of existing tools and with a brief discussion of the big open problems in the area. Index Terms--Duplicate detection, data cleaning, data integration, record linkage, data deduplication, instance identification, database hardening, name matching, identity uncertainty, entity resolution, fuzzy duplicate detection, entity matching.

The contents of many valuable Web-accessible databases are only available through search interfaces and are hence invisible to traditional Web "crawlers." Recently, commercial Web sites have started to manually organize Web-accessible databases into Yahoo!-like hierarchical classification schemes. Here we introduce QProber, a modular system that automates this classification process by using a small number of query probes, generated by document classifiers. QProber can use a variety of types of classifiers to generate the probes. To classify a database, QProber does not retrieve or inspect any documents or pages from the database, but rather just exploits the number of matches that each query probe generates at the database in question. We have conducted an extensive experimental evaluation of QProber over collections of real documents, experimenting with different types of document classifiers and retrieval models. We have also tested our system with over one hundred Web-accessible databases. Our experiments show that our system has low overhead and achieves high classification accuracy across a variety of databases. Categories and Subject Descriptors: H.3.1 [Content Analysis and Indexing]: Abstracting Methods; H.3.3 [Information Storage and Retrieval]: Information Search and Retrieval--clustering, information filtering, search process, selection process; H.3.4 [Systems and Software]: Information Networks, Performance Evaluation (efficiency and effectiveness); H.3.5 [Information Storage and Retrieval]: Online Information Services--web-based services; H.3.7 [Information Storage and Retrieval]: Digital Libraries; H.2.4 [Database Management]: Systems--textual databases, distributed databases; H.2.5 [Database Management]: Systems--heterogeneous databases General Terms: Algorithms, Experimentation, Performance Additional Key Words and Phrases: Database classification, Web databases, hidden Web