waashk/dblp huggingface dataset:
optimizing candidate check costs for bitmap indices. in this paper, we propose a new strategy for optimizing the placement of bin boundaries to minimize the cost of query evaluation using bitmap indices with binning. for attributes with a large number of distinct values, often the most efficient index scheme is a bitmap index with binning. however, this type of index may not be able to fully resolve some user queries. to fully resolve these queries, one has to access parts of the original data to check whether certain candidate records actually satisfy the specified conditions. we call this procedure the candidate check, which usually dominates the total query processing time. given a set of user queries, we seek to minimize the total time required to an-swer the queries by optimally placing the bin boundaries. we show that our dynamic programming based algorithm can efficiently determine the bin boundaries. we verify our analysis with some real user queries from the sloan digital sky survey. for queries that require significant amount of time to perform candidate check, using our optimal bin boundaries reduces the candidate check time by a factor of 2 and the total query processing time by 40%.
semantic verification for fact seeking engines. we present the architecture of our web question answering (fact seeking) system and introduce a novel algorithm to validate semantic categories of the expected answers. when tested on the questions used by the prior research, our system demonstrated the performance comparable to the current state of the art systems. our semantic verification algorithm has improved the accuracy of answers of the affected questions by 30%.
discretization based learning approach to information retrieval. we have designed a representation scheme, which is based on the discrete representation of a document ranking function, which is capable of reproducing and enhancing the properties of such popular ranking functions as tf.idf, bm25 or those based on language models. our tests have demonstrated the capability of our approach to achieve the performance of the best known scoring functions solely through training, without using any known heuristic or analytic formulas.
towards automatic association of relevant unstructured content with structured query results. faced with growing knowledge management needs, enterprises are increasingly realizing the importance of seamlessly integrating critical business information distributed across both structured and unstructured data sources. in existing information integration solutions, the application needs to formulate the sql logic to retrieve the needed structured data on one hand, and identify a set of keywords to retrieve the related unstructured data on the other. this paper proposes a novel approach wherein the application specifies its information needs using only a sql query on the structured data, and this query is automatically ``translated'' into a set of keywords that can be used to retrieve relevant unstructured data. we describe the techniques used for obtaining these keywords from (i) the query result, and (ii) additional related information in the underlying database. we further show that these techniques achieve high accuracy with very reasonable overheads.
a classification algorithm for supporting object-oriented views. in recent years, object-oriented (oo) views have been recognized as a powerful mechanism for customizing the structural as well as behavioral aspects of interfaces to object-oriented databases (oodbs) for diverse users. in this context, classification is concerned with the integration of virtual classes derived using an oo query into one unifying schema. existing approaches either require the user to explicitly specify the relationship between a virtual class and existing base classes, or they relate a virtual class directly with its source class(es) or with the root of the schema. in this paper, we propose a solution to this classification problem that accomplishes the following goals: (1) generate maximally informative, and thus comprehensible, schemas that explicitly model the subclass relationships between base and virtual classes, and (2) support efficient type resolution for shared property functions by supporting upwards inheritance for both base and virtual classes. correctness and complexity of the classification algorithm are also discussed.
self maintenance of multiple views in data warehousing. materialized views (mv) at the data warehouse (dw) can be kept up to date in response to changes in data sources without accessing data sources for additional information. this process is usually refered to as &ldquo;self maintenance of views&rdquo;. a number of algorithms have been proposed for self maintenance of views, which use auxiliary views (av) to keep some additional information in dw. in this paper we propose an algorithm for self maintainability of multiple mvs using the above approach. our algorithm generates a simple maintenance query to incrementally maintain an mv along with its av at dw. the algorithm maintains these views by minimizing the number and the size of the avs. our approach provides better insight into view maintenance issues by exploiting the dependencies and constraints that might exist in the data sources and multiple mvs at dw.
structural inference for semistructured data. semistructured data presents many challenges, mainly due to its lack of a strict schema. these challenges are further magnified when large amounts of data are gathered from heterogeneous sources. we address this by investigation and development of methods to automatically infer structural information from example data. using xml as a reference format, we approach the schema generation problem by application of inductive inference theory. in doing so, we review and extend results relating to the search spaces of grammatical inferences. we then adapt a method for evaluating the result of an inference process from computational linguistics. further, we combine several inference algorithms, including both new techniques introduced by us and those from previous work. comprehensive experimentation reveals our new hybrid method, based upon recently developed optimisation techniques, to be the most effective.
circumstance-based categorization analysis of knowledge management systems for the japanese market. we conducted a survey of thirty of the approximately 1,700 customers of justsystem corporation's knowledge-management applications. our goal was to discover the kinds of functions that customers hoped to address in their next-generation use of knowledge management technology and to assess the core processes that we will need to deploy in our products to address their desired solutions. in particular, we sought to analyze our customers' requirements along dimensions that take account of both the context of use of the application and its stage in the cycle of knowledge creation and use. as part of our analysis, we were able to classify all customer cases as focused by one or more of three goals, supported by one or more of eleven technology means. to establish appropriate categories of use, we exploited the stages of the <i>seci model</i>, several other transactional categories of knowledge use, and whether activities were targeted at internal or external users. through the analysis, we found the typical technology components (means) for each stage of knowledge creation and use associated with each set of goals. we consider such analysis essential to the task of designing next-generation knowledge-management applications and critical to overcoming the unfortunate tendency of developers to devise solutions that bear little relation to the true needs of users.
sql database primitives for decision tree classifiers. scalable data mining in large databases is one of today's challenges to database technologies. thus, substantial effort is dedicated to a tight coupling of database and data mining systems leading to database primitives supporting data mining tasks. in order to support a wide range of tasks and to be of general usage these primitives should be rather building blocks than implementations of specific algorithms. in this paper, we describe primitives for building and applying decision tree classifiers. based on the analysis of available algorithms and previous work in this area we have identified operations which are useful for a number of classification algorithms. we discuss the implementation of these primitives on top of a commercial dbms and present experimental results demonstrating the performance benefit.
meta-recommendation systems: user-controlled integration of diverse recommendations. in a world where the number of choices can be overwhelming, recommender systems help users find and evaluate items of interest. they do so by connecting users with information regarding the content of recommended items or the opinions of other individuals. such systems have become powerful tools in domains such as electronic commerce, digital libraries, and knowledge management. in this paper, we address such systems and introduce a new class of recommender system called meta-recommenders. meta-recommenders provide users with personalized control over the generation of a single recommendation list formed from a combination of rich data using multiple information sources and recommendation techniques. we discuss experiments conducted to aid in the design of interfaces for a meta-recommender in the domain of movies. we demonstrate that meta-recommendations fill a gap in the current design of recommender systems. finally, we consider the challenges of building real-world, usable meta-recommenders across a variety of domains.
advanced grouping and aggregation for data integration. new applications from the areas of analytical data processing and data integration require powerful features to condense and reconcile available data. as outlined in [1], the general concept of grouping and aggregation appears to be a fitting paradigm for a number of these issues, but in its common form of equality based groups or with current extensions like simple user-defined functions to derive group-by values on a per tuple basis and restricted aggregate functions a number of problems remain unsolved. we describe two extensions to the grouping mechanism, a generic one to support holistic user-defined grouping functions and higher level construct that provides similarity based grouping suitable in a number of applications like duplicate detection and elimination.
query association for effective retrieval. we introduce a novel technique for document summarisation which we call query association. query association is based on the notion that a query that is highly similar to a document is a good descriptor of that document. for example, the user query "richmond football club" is likely to be a good summary of the content of a document that is ranked highly in response to the query. we describe this process of defining, maintaining, and presenting the relationship between a user query and the documents that are retrieved in response to that query. we show that associated queries are an excellent technique for describing a document: for relevance judgement, associated queries are as effective as a simple online query-biased summarisation technique. as future work, we suggest additional uses for query association including relevance feedback and query expansion.
boosting support vector machines for text classification through parameter-free threshold relaxation. support vector machine (svm) learning algorithms focus on finding the hyperplane that maximizes the margin (the distance from the separating hyperplane to the nearest examples) since this criterion provides a good upper bound of the generalization error. when applied to text classification, these learning algorithms lead to svms with excellent precision but poor recall. various relaxation approaches have been proposed to counter this problem including: asymmetric svm learning algorithms (soft svms with asymmetric misclassification costs); uneven margin based learning; and thresholding. a review of these approaches is presented here. in addition, in this paper, we describe a new threshold relaxation algorithm. this approach builds on previous thresholding work based upon the beta-gamma algorithm. the proposed thresholding strategy is parameter free, relying on a process of retrofitting and cross validation to set algorithm parameters empirically, whereas our previous approach required the specification of two parameters (beta and gamma). the proposed approach is more efficient, does not require the specification of any parameters, and similarly to the parameter-based approach, boosts the performance of baseline svms by at least 20% for standard information retrieval measures.
index construction for linear categorisation. categorisation is a useful method for organising documents into subcollections that can be browsed or searched to more accurately and quickly meet information needs. on the web, category-based portals such as yahoo! and dmoz are extremely popular: dmoz is maintained by over 56,000 volunteers, is used as the basis of the popular google directory, and is perhaps used by millions of users each day. support vector machines (svm) is a machine-learning algorithm which has been shown to be highly effective for automatic text categorisation. however, a problem with iterative training techniques such as svm is that during their learning or training phase, they require the entire training collection to be held in main-memory; this is infeasible for large training collections such as dmoz or large news wire feeds. in this paper, we show how inverted indexes can be used for scalable training in categorisation, and propose novel heuristics for a fast, accurate, and memory efficient approach. our results show that an index can be constructed on a desktop workstation with little effect on categorisation accu-racy compared to a memory-based approach. we conclude that our techniques permit automatic categorisation using very large train-ing collections, vocabularies, and numbers of categories.
semantic-based delivery of olap summary tables in wireless environments. with the rapid growth in mobile and wireless technologies and the availability, pervasiveness and cost effectiveness of wireless networks, mobile computers are quickly becoming the normal front-end devices for accessing enterprise data. in this paper, we are addressing the issue of efficient delivery of business decision support data in the form of summary tables to mobile clients equipped with olap front-end tools. towards this, we propose a new on-demand scheduling algorithm, called sbs, that exploits both the derivation semantics among olap summary tables and the mobile clients' capabilities of executing simple sql queries. it maximizes the aggregated data sharing between clients and reduces the broadcast length compared to the already existing techniques. the degree of aggregation can be tuned to control the tradeoff between access time and energy consumption. further, the proposed scheme adapts well to different request rates, access patterns and data distributions. the algorithm effectiveness with respect to access time and power consumption is evaluated using simulation.
finding similar images quickly using object shapes. retrieving images from a large image collection has been an active area of research. most of the existing works have focused on content representation. in this paper, we address the issue of identifying relevant images quickly. this is important in order to meet the users' performance requirements. we propose a framework for fast image retrieval based on object shapes extracted from objects within images. the framework builds a hierarchy of approximations on object shapes such that shape representation at a higher level is a coarser representation of a shape at the lower level. in other words, multiple shapes at a lower level can be mapped into a single shape at a higher level. in this way, the hierarchy serves to partition the database at various granularities. given a query shape, by searching only the relevant paths in the hierarchy, a large portion of the database can thus be pruned away. we propose the angle mapping (am) method to transform a shape from one level to another (higher) level. am essentially replaces some edges of a shape by a smaller number of edges based on the angles between the edges, thus reducing the complexity of the original shape. based on the framework, we also propose two hierarchical structures to facilitate speedy retrieval. the first, called hierarchical partitioning on shape representation (hpsr), uses the shape representation as the indexing key. the second, called hierarchical partitioning on angle vector (hpav), captures the angle information from the shape representation. we conducted an extensive study on both methods to see their quality and efficiency. our experiments on sets of images, each of which has objects around from 1 to 30, showed that the framework can provide speedy image retrieval without sacrificing on the quality. both proposed schemes can improve the efficiency by as much as hundreds of times to sequential scanning. the improvement grows as image database size, objects per image or object dimension increase.
integrating heterogeneous reatures for efficient content based music retrieval. in this paper, we present a novel feature extraction method facilitating efficient content-based music retrieval and classification, called <i>inmaf</i>. the goal of our approach is to allow straightforward incorporation of multiple musical features, such as timbral texture, pitch and rhythm structure, into a single low dimensional vector that is effective for retrieval and classification. unlike earlier approaches that used only acoustic properties as the basis for retrieval, our approach can easily incoporate human music perception to improve accuracy of retrieval and classification process. the superiority of our method is demonstrated by comparing it with state-of-the-art approaches in the areas of music classification (using a variety of machine learning algorithms), query effectiveness and robustness against audio distortion.
implicit user modeling for personalized search. information retrieval systems (e.g., web search engines) are critical for overcoming information overload. a major deficiency of existing retrieval systems is that they generally lack user modeling and are not adaptive to individual users, resulting in inherently non-optimal retrieval performance. for example, a tourist and a programmer may use the same word "java" to search for different information, but the current search systems would return the same results. in this paper, we study how to infer a user's interest from the user's search context and use the inferred implicit user model for personalized search. we present a decision theoretic framework and develop techniques for implicit user modeling in information retrieval. we develop an intelligent client-side web search agent (ucair) that can perform eager implicit feedback, e.g., query expansion based on previous queries and immediate result reranking based on clickthrough information. experiments on web search show that our search agent can improve search accuracy over the popular google search engine.
leonardo's laptop: human needs and the new computing technologies. the old computing was about what computers could do; the new computing is about what people can do.to accelerate the shift from the old to the new computing designers need to:reduce computer user frustration. recent studies show 46% of time is lost to crashes, confusing instructions, navigation problems, etc. public pressure for change could promote design improvements and increase reliability, thereby dramatically enhancing user experiences.promote universal usability. interfaces must be tailorable to a wide range of hardware, software, and networks, and users. when broad services such as voting, healthcare, and education are envisioned, the challenge to designers is substantial.envision a future in which human needs more directly shape technology evolution. four circles of human relationships and four human activities map out the human needs for mobility, ubiquity, creativity, and community. the world wide med and million-person communities will be accessible through desktop, palmtop and fingertip devices to support e-learning, e-business, e-healthcare, and e-government.leonardo da vinci could help as an inspirational muse for the new computing. his example could push designers to improve quality through scientific study and more elegant visual design. leonardo's example can guide us to the new computing, which emphasizes empowerment, creativity, and collaboration. information visualization and personal photo interfaces will be shown: photomesa (www.cs.umd.edu/hcil/photomesa) and photofinder (www.cs.umd.edu/hcil/photolib).for more: http://mitpress.mit.edu/leonardoslaptop and http://www.cs.umd.edu/hcil/newcomputing.
performance of clustering policies in object bases. in this paper, we address the problem of clustering graphs in object-oriented databases. unlike previous studies which focused only on a workload consisting of a single operation, this study tackles the problem when the workload is a set of operations (method and queries) that occur with a certain probability. thus, the goal is to minimize the expected cost of an operation in the workload, while maintaining a similarly low cost for each individual operation class.to this end, we present a new clustering policy based on the nearest-neighbor graph partitioning algorithm. we then demonstrate that this policy provides considerable gains when compared to a suite of well-known clustering policies proposed in the literature. our results are based on two widely referenced object-oriented database benchmarks; namely, the tektronix hypermodel and oo7.
discovering quasi-equivalence relationships from database systems. association rule mining has recently attracted strong attention and proven to be a highly successful technique for extracting useful information from very large databases. in this paper, we explore a generalized affinity-based association mining which discovers quasi-equivalent media objects in a distributed information-providing environment consisting of a network of heterogeneous databases which could be relational databases, hierarchical databases, object-oriented databases, multimedia databases, etc. online databases, consisting of millions of media objects, have been used in business management, government administration, scientific and engineering data management, and many other applications owing to the recent advances in high-speed communication networks and large-capacity storage devices. because of the navigational characteristic, queries in such an information-providing environment tend to traverse equivalent media objects residing in different databases for the related data records. as the number of databases increases, query processing efficiency depends heavily on the capability to discover the equivalence relationships of the media objects from the network of databases. theoretical terms along with an empirical study of real databases are presented.
a language modeling framework for resource selection and results merging. statistical language models have been proposed recently for several information retrieval tasks, including the resource selection task in distributed information retrieval. this paper extends the language modeling approach to integrate resource selection, ad-hoc searching, and merging of results from different text databases into a single probabilistic retrieval model. this new approach is designed primarily for intranet environments, where it is reasonable to assume that resource providers are relatively homogeneous and can adopt the same kind of search engine. experiments demonstrate that this new, integrated approach is at least as effective as the prior state-of-the-art in distributed ir.