Search

Wireless data broadcast allows a large number of users to retrieve data simultaneously in mobile databases, resulting in an efficient way of using the scarce wireless bandwidth. However, the efficiency of data access methods is limited by an inherent property that data can only be accessed strictly sequentially by users. To properly cope with the inherent property, this paper presents three predaclaration-based transaction processing methods that yield a significant performance improvement in wireless data broadcast. [ABSTRACT FROM AUTHOR]

Focuses on the importance of finding subjects of photographic image on the concise papers. Development of digital image on the multimedia caption; Determination of visual focus on the segmented image; Identification of ranking on the photograph.

A functional $k$ -batch code of dimension $s$ consists of $n$ servers storing linear combinations of $s$ linearly independent information bits. Any multiset request of size $k$ of linear combinations (or requests) of the information bits can be recovered by $k$ disjoint subsets of the servers. The goal under this paradigm is to find the minimum number of servers for given values of $s$ and $k$. A recent conjecture states that for any $k=2^{s-1}$ requests the optimal solution requires $2^{s}-1$ servers. This conjecture is verified for $s \leqslant 5$ but previous work could only show that codes with $n=2^{s}-1$ servers can support a solution for $k=2^{s-2} + 2^{s-4} + \left \lfloor{ \frac { 2^{s/2}}{\sqrt {24}} }\right \rfloor $ requests. This paper reduces this gap and shows the existence of codes for $k=\lfloor \frac {5}{6}2^{s-1} \rfloor - s$ requests with the same number of servers. Another construction in the paper provides a code with $n=2^{s+1}-2$ servers and $k=2^{s}$ requests, which is an optimal result. These constructions are mainly based on extended Simplex codes and equivalently provide constructions for parallel Random I/O (RIO) codes. [ABSTRACT FROM AUTHOR]

A private proximity retrieval (PPR) scheme is a protocol which allows a user to retrieve the identities of all records in a database that are within some distance $r$ from the user’s record $x$. The user’s privacy at each server is given by the fraction of the record $x$ that is kept private. In this paper, this research is initiated and protocols that offer trade-offs between privacy, computational complexity, and storage are studied. In particular, we assume that each server stores a copy of the database and study the required minimum number of servers by our protocol which provides a given privacy level. Each server receives a query in the protocol and the set of queries forms a code. The main focus in the paper is dedicated to studying the family of codes generated by the set of queries. These codes will be shown to satisfy a specific covering property and will be called private proximity retrieval intersection covering codes. In particular, since the query every server receives is a codeword, the goal is to minimize the number of codewords in such a code which is the minimum number of servers required by the protocol. These codes are closely related to a family of codes known as covering designs. We introduce several lower bounds on the sizes of such codes as well as several constructions. This work focuses on the case when the records are binary vectors together with the Hamming distance. Other metrics such as the Johnson metric are also investigated. [ABSTRACT FROM AUTHOR]

Short text clustering has far-reaching effects on semantic analysis, showing its importance for multiple applications such as corpus summarization and information retrieval. However, it inevitably encounters the severe sparsity of short text representations, making the previous clustering approaches still far from satisfactory. In this paper, we present a novel attentive representation learning model for shot text clustering, wherein cluster-level attention is proposed to capture the correlations between text representations and cluster representations. Relying on this, the representation learning and clustering for short texts are seamlessly integrated into a unified model. To further ensure robust model training for short texts, we apply adversarial training to the unsupervised clustering setting, by injecting perturbations into the cluster representations. The model parameters and perturbations are optimized alternately through a minimax game. Extensive experiments on four real-world short text datasets demonstrate the superiority of the proposed model over several strong competitors, verifying that robust adversarial training yields substantial performance gains. [ABSTRACT FROM AUTHOR]

The empirical nature of Information Retrieval (IR) mandates strong experimental practices. A keystone of such experimental practices is the Cranfield evaluation paradigm. Within this paradigm, the collection of relevance judgments has been the subject of intense scientific investigation. This is because, on one hand, consistent, precise, and numerous judgements are keys to reducing evaluation uncertainty and test collection bias; on the other hand, however, relevance judgements are costly to collect. The selection of which documents to judge for relevance, known as pooling method, has therefore a great impact on IR evaluation. In this paper we focus on the bias introduced by the pooling method, known as pool bias, which affects the reusability of test collections, in particular when building test collections with a limited budget. In this paper we formalize and evaluate a set of 22 pooling strategies based on: traditional strategies, voting systems, retrieval fusion methods, evaluation measures, and multi-armed bandit models. To do this we run a large-scale evaluation by considering a set of 9 standard TREC test collections, in which we show that the choice of the pooling strategy has significant effects on the cost needed to obtain an unbiased test collection. We also identify the least biased pooling strategy in terms of pool bias according to three IR evaluation measures: AP, NDCG, and P@10. [ABSTRACT FROM AUTHOR]

Forward modeling of wave scattering and radar imaging mechanisms is the key to information extraction from synthetic aperture radar (SAR) images. Like inverse graphics in the optical domain, an inherently-integrated forward-inverse approach would be promising for SAR advanced information retrieval and target reconstruction. This paper presents such an attempt at inverse graphics for SAR imagery. A differentiable SAR renderer (DSR) is developed, which reformulates the mapping and projection algorithm of the SAR imaging mechanism in the differentiable form of probability maps. First-order gradients of the proposed DSR are then analytically derived, which can be back-propagated from rendered image/silhouette to the target geometry and scattering attributes. A 3D inverse target reconstruction algorithm from SAR images is devised. Several simulation and reconstruction experiments are conducted, including targets with and without background, using synthesized data or real measured inverse SAR (ISAR) data by ground radar. Results demonstrate the efficacy of the proposed DSR and its inverse approach. [ABSTRACT FROM AUTHOR]

A fundamental technique in machine learning called “embedding” has made significant impact on data representation. Some examples of embedding include word embedding, image embedding and audio embedding. With the embedding techniques, many real-world objects can be represented using matrices. For example, a document can be represented by a matrix, where each row of the matrix represents a word. On the other hand, we have witnessed that many applications continuously generate new data represented by matrices and require real-time query answering on the data. These continuously generated matrices need to be well managed for efficient retrieval. In this paper, we propose a high-performance index for real-time matrix retrieval. Besides fast query response, the index also supports real-time insertion by exploiting the log-structured merge-tree (LSM-tree). Since the index is built for matrices, it consumes much more memory and requires much more time to search than the traditional index for information retrieval. To tackle the challenges, we propose an index with precise and fuzzy inverted lists, and design a series of novel techniques to improve the memory consumption and the search efficiency of the index. The proposed techniques include vector signature, vector residual sorting, hashing based lookup, and dictionary initialization to guarantee the index quality. Comprehensive experimental results show that our proposed index can support real-time search on matrices, and is more time and memory efficient than the state-of-the-art method. [ABSTRACT FROM AUTHOR]

The increasing amount of graph-structured data catalyzes analytics over graph databases using semantic queries. Motivated by the ubiquity of commercial cloud platforms, data owners are willing to store their graph databases remotely. However, data privacy has emerged as a widespread concern since the cloud platforms are not fully trusted. One viable solution is to encrypt sensitive data before outsourcing, which inevitably hinders data retrieval. To enable queries over encrypted data, searchable symmetric encryption (SSE) has been introduced. Yet, the most well-studied class of SSE schemes focuses on retrieving textual files given keywords, which cannot be applied to graph databases directly. This paper extends our preliminary work (FC’17) and proposes GraphShield, a structured encryption scheme for graphs. Beyond shortest distance queries, GraphShield can support other classic graph-based queries (e.g., maximum flow) and more complicated analytics (e.g., PageRank). Technically, we incorporate a suite of (efficient) cryptographic primitives and tailor some extra secure protocols for facilitating graph analytics. Our scheme also allows updates on the encrypted graph with forward privacy guaranteed. We formalize the security model and prove the adaptive security with reasonable leakage. Finally, we implement our scheme on various real-world datasets, and the experiment results demonstrate its practicality and scalability. [ABSTRACT FROM AUTHOR]

Quantum cybersecurity is the study of all facets regarding the security of communication and computation in a distributed network. Significant developments in quantum technologies have outclassed their classical counterparts, thus envisioning the realization of a quantum internet. However, such quantum resources, in the hands of an adversary, can jeopardize network security. In this paper, we study two secure network connectivity concerns, namely, privacy and anonymity, in quantum information retrieval systems. To this end, we propose a state-of-the-art single-server multi-user quantum anonymous private information retrieval (QAPIR) protocol. To actualize this, we utilize anonymous entanglement as a quantum resource. We show that the QAPIR protocol not only provides privacy but also introduces anonymity as an added layer of security in quantum networks. Furthermore, we also detail a comparative security analysis that establishes the desirable properties of our proposal. [ABSTRACT FROM AUTHOR]

With the development of cloud computing, more and more data owners are motivated to outsource their documents to the cloud and share them with the authorized data users securely and flexibly. To protect data privacy, the documents are generally encrypted before being outsourced to the cloud and hence their searchability decreases. Though many privacy-preserving document search schemes have been proposed, they cannot reach a proper balance among functionality, flexibility, security and efficiency. In this paper, a new encrypted document retrieval system is designed and a proxy server is integrated into the system to alleviate data owner's workload and improve the whole system's security level. In this process, we consider a more practical and stronger threat model in which the cloud server can collude with a small number of data users. To support multiple document search patterns, we construct two AVL trees for the filenames and authors, and a Hierarchical Retrieval Features tree (HRF tree) for the document vectors. A depth-first search algorithm is designed for the HRF tree and the Enhanced Asymmetric Scalar-Product-Preserving Encryption (Enhanced ASPE) algorithm is utilized to encrypt the HRF tree. All the three index trees are linked with each other to efficiently support the search requests with multiple parameters. Theoretical analysis and simulation results illustrate the security and efficiency of the proposed framework. [ABSTRACT FROM AUTHOR]

Support for efficient spatial data storage and retrieval has become a vital component in almost all spatial database systems. While GPUs have become a mainstream platform for high-throughput data processing in recent years, exploiting the massively parallel processing power of GPUs is non-trivial. Current approaches that parallelize one query at a time have low work efficiency and cannot make good use of GPU resources. On the other hand, many spatial database systems could receive a large number of queries simultaneously. In this paper, we present a comprehensive framework named G-PICS for parallel processing of concurrent spatial queries on GPUs. G-PICS encapsulates efficient parallel algorithms for constructing a variety of spatial trees with different space partitioning methods. G-PICS also provides highly optimized programs for processing major spatial query types, and such programs can be accessed via an API that could be further extended to implement user-defined algorithms. While support for dynamic data inputs is missing in existing work, G-PICS implements efficient parallel algorithms for bulk updates of data. Furthermore, G-PICS is designed to work in a Multi-GPU environment to support datasets beyond the size of a single GPU’s global memory. Empirical evaluation of G-PICS shows significant performance improvement over the state-of-the-art GPU and parallel CPU-based spatial query processing systems. In particular, G-PICS achieves double-digit speedup over such systems in tree construction (up to 53X) and query processing (up to 80X). [ABSTRACT FROM AUTHOR]

A functional PIR array code is a coding scheme which encodes some $s$ information bits into a $t\times m$ array such that every linear combination of the $s$ information bits has $k$ mutually disjoint recovering sets. Every recovering set consists of some of the array’s columns while it is allowed to read at most $\ell $ encoded bits from every column in order to receive the requested linear combination of the information bits. Functional batch array codes impose a stronger property where every multiset request of $k$ linear combinations has $k$ mutually disjoint recovering sets. Locality functional array codes demand that the size of every recovering set is restrained to be at most $r$. Given the values of $s, k, t, \ell,r$ , the goal of this paper is to study the optimal value of the number of columns $m$ such that these codes exist. Several lower bounds are presented as well as explicit constructions for several of these parameters. [ABSTRACT FROM AUTHOR]

In the classical model for (information theoretically secure) Private Information Retrieval (PIR) due to Chor, Goldreich, Kushilevitz and Sudan, a user wishes to retrieve one bit of a database that is stored on a set of ${n}$ servers, in such a way that no individual server gains information about which bit the user is interested in. The aim is to design schemes that minimise the total communication between the user and the servers. More recently, there have been moves to consider more realistic models where the total storage of the set of servers, or the per server storage, should be minimised (possibly using techniques from distributed storage), and where the database is divided into ${R}$ -bit records with ${R}>1$ , and the user wishes to retrieve one record rather than one bit. When ${R}$ is large, downloads from the servers to the user dominate the communication complexity and so the aim is to minimise the total number of downloaded bits. Work of Shah, Rashmi and Ramchandran shows that at least ${R}+1$ bits must be downloaded from servers in the worst case, and provides PIR schemes meeting this bound. Sun and Jafar have considered the download cost of a scheme, defined as the ratio of the message length ${R}$ and the total number of bits downloaded. They determine the best asymptotic download cost of a PIR scheme (as ${R}\rightarrow \infty $) when a database of ${k}$ messages is stored by ${n}$ servers. This paper provides various bounds on the download complexity of a PIR scheme, generalising those of Shah et al. to the case when the number ${n}$ of servers is bounded, and providing links with classical techniques due to Chor et al. The paper also provides a range of constructions for PIR schemes that are either simpler or perform better than previously known schemes. These constructions include explicit schemes that achieve the best asymptotic download complexity of Sun and Jafar with significantly lower upload complexity, and general techniques for constructing a scheme with good worst case download complexity from a scheme with good download complexity on average. [ABSTRACT FROM AUTHOR]

There has been much recent interest in private information retrieval (PIR) in models where a database is stored across several servers using coding techniques from distributed storage, rather than being a simply replicated. In particular, a recent breakthrough result of Fazelli, Vardy, and Yaakobi introduces the notion of a PIR code and a PIR array code, and uses this notion to produce efficient PIR protocols. In this paper, we are interested in designing PIR array codes. We consider the case when we have $m$ servers, with each server storing a fraction $(1/s)$ of the bits of the database; here $s$ is a fixed rational number with $s > 1$. A PIR array code with the $k$ -PIR property enables a $k$ -server PIR protocol (with $k\leq m$) to be emulated on $m$ servers, with the overall storage requirements of the protocol being reduced. The communication complexity of a PIR protocol reduces as $k$ grows, so the virtual server rate, defined to be $k/m$ , is an important parameter. We study the maximum virtual server rate of a PIR array code with the $k$ -PIR property. We present upper bounds on the achievable virtual server rate, some constructions, and ideas how to obtain the PIR array codes with the highest possible virtual server rate. In particular, we present constructions that asymptotically meet our upper bounds and the exact largest virtual server rate is obtained when $1 < s \leq 2$. A $k$ -PIR code (and similarly a $k$ -PIR array code) is also a locally repairable code with symbol availability $k-1$. Such a code ensures $k$ parallel reads for each information symbol. So the virtual server rate is very closely related to the symbol availability of the code when used as a locally repairable code. The results of this paper are discussed also in this context where subspace codes also have an important role. [ABSTRACT FROM AUTHOR]

The $T$ -Private Information Retrieval ($T$ -PIR) problem is that a user wishes to retrieve a single record from $N$ servers, without revealing the identity of the desired record even if the number of colluding servers up to $T$. Here every server stores all $M$ records and each record can be viewed as a vector over the $q$ -ary finite field $\mathbb {F}_{q}$. To reduce the field size, a capacity-achieving $T$ -PIR scheme based on some MDS array codes for all possible $N>T,M\geq 2$ was constructed by Xu and Zhang in 2019. A key idea in that scheme is to construct some MDS array codes in query phase, whose generator matrices satisfy the recovery property (see (C1) in , page 6), i.e., there exist some specific columns in each generator matrix such that the number of them is equal to the rank of such matrix. We call the set of each column index of those columns in each generator matrix as the column index set. However, that scheme didn’t give an explicit selection of the column index set satisfying the recovery property. In this paper, let $N=d(2t-1)$ , $N>T=dt>1, M\geq 3$ and $d\geq 1$ , under the constraint of $2^{t-1}\geq N$ , we present a novel method to construct capacity-achieving $T$ -PIR schemes over the binary field with an explicit selection of the column index set. Moreover, our scheme has sub-packetization $N(2t-1)^{M-2}$ , which is optimal for all linear capacity-achieving $T$ -PIR schemes determined by Zhang and Xu in 2019. The key to our method is that all locators and column multipliers are precisely selected such that a Generalized Reed-Solomon (GRS) code defined by them has a zero-dimensional subfield sub-code. Compared with all the known capacity-achieving $T$ -PIR schemes for the same non-trivial parameters, ours is the first explicit capacity-achieving $T$ -PIR scheme over the binary field. [ABSTRACT FROM AUTHOR]

The fundamental limits of private information retrieval (PIR) with unknown cache prefetching at the user are investigated in this paper. To this end, a novel random linear combination (RLC)-based PIR scheme that can solve the basic PIR problem and its variation is proposed. The proposed scheme is based on random coding approach and achieves the capacity of the basic PIR asymptotically. Then, we investigate PIR with unknown cache prefetching (PIRC) problem at different cache-to-file size ratio. Specifically, we propose RLC-based PIRC method, which prefetches RLC-based side information and leverages them to retrieve desired information at small download cost. Furthermore, by applying time and memory sharing on the proposed RLC-based PIRC, RLC-based basic PIR and some other known approach in literature, we derive the achievable normalized download cost bound of PIRC. The derived achievable bound outperforms the existing bound in literature and the case study provides numerical results that verifies it. [ABSTRACT FROM AUTHOR]

Hashing methods have been extensively applied to efficient multimedia data indexing and retrieval on account of the explosion of multimedia data. Cross-modal hashing usually learns binary codes by mapping multi-modal data into a common Hamming space. Most supervised methods utilize relation information like class labels as pairwise similarities of cross-modal data pair to narrow intra-modal and inter-modal gap. In this paper, we propose a novel supervised cross-modal hashing method dubbed Subspace Relation Learning for Cross-modal Hashing (SRLCH), which exploits relation information of labels in semantic space to make similar data from different modalities closer in the low-dimension Hamming subspace. SRLCH preserves the modality relationships, the discrete constraints and nonlinear structures, while admitting a closed-form binary codes solution, which effectively enhances the training efficiency. An iterative alternative optimization algorithm is developed to simultaneously learn both hash functions and unified binary codes. With these binary codes and hash functions, we can index multimedia data and search them in an efficient way. Evaluations in two cross-modal retrieval tasks on several widely-used datasets show that the proposed SRLCH outperforms most cross-modal hashing methods. Theoretical analysis also illustrates reasons for our method’s promotion in subspace relation learning. [ABSTRACT FROM AUTHOR]

Ranking on graphs is a centerpiece in many high-impact application domains, such as information retrieval, recommender systems, team management, neuroscience and many more. PageRank, along with many of its variants, is widely used across these application domains thanks to its mathematical elegance and the superior performance. Although PageRank and its variants are effective in ranking nodes on graphs, they often lack an efficient and effective way to audit the ranking results in terms of the input graph structure, e.g., which node or edge in the graph contributes most to the top-1 ranked node; which subgraph plays a crucial role in generating the overall ranking result? In this paper, we propose to audit graph ranking by finding the influential graph elements (e.g., edges, nodes, attributes, and subgraphs) regarding their impact on the ranking results. First, we formulate graph ranking auditing problem as quantifying the influence of graph elements on the ranking results. Second, we show that our formulation can be applied to a variety of graph structures. Third, we propose effective and efficient algorithms to find the top- $k$ k influential edges/nodes/subgraph. Finally, we perform extensive empirical evaluations on real-world datasets to demonstrate that the proposed methods (Aurora) provide intuitive auditing results with linear scalability. [ABSTRACT FROM AUTHOR]

We consider the problem of cache-aided Multiuser Private Information Retrieval (MuPIR) which is an extension of the single-user cache-aided PIR problem to the case of multiple users. In cache-aided MuPIR, each of the $K_{\mathrm{ u}}$ cache-equipped users wishes to privately retrieve a message out of $K$ messages from $N$ databases each having access to the entire message library. Demand privacy requires that any individual database learns nothing about the demands of all users. The users are connected to each database via an error-free shared-link. In this paper, we aim to characterize the optimal trade-off between user cache memory and communication load for such systems. First, we propose a novel approach of cache-aided interference alignment (CIA), for the MuPIR problem with $K=2$ messages, $K_{\mathrm{ u}}=2$ users and $N\ge 2$ databases. The CIA approach is optimal when the cache placement is uncoded. For general cache placement, the CIA approach is optimal when $N=2$ and 3 verified by the computer-aided converse approach. Second, for the general case, we propose a product design (PD) which incorporates the PIR code into the linear caching code. The product design is shown to be order optimal within a multiplicative factor of 8 and is exactly optimal in the high memory regime. [ABSTRACT FROM AUTHOR]

Information-theoretic formulations of the private information retrieval (PIR) problem have been investigated under a variety of scenarios. Symmetric private information retrieval (SPIR) is a variant where a user is able to privately retrieve one out of K messages from N non-colluding replicated databases without learning anything about the remaining K−1 messages. However, the goal of perfect privacy can be too taxing for certain applications. In this paper, we investigate if the information-theoretic capacity of SPIR (equivalently, the inverse of the minimum download cost) can be increased by relaxing both user and DB privacy definitions. Such relaxation is relevant in applications where privacy can be traded for communication efficiency. We introduce and investigate the Asymmetric Leaky PIR (AL-PIR) model with different privacy leakage budgets in each direction. For user privacy leakage, we bound the probability ratios between all possible realizations of DB queries by a function of a non-negative constant ε. For DB privacy, we bound the mutual information between the undesired messages, the queries, and the answers, by a function of a non-negative constant &#948. We propose a general AL-PIR scheme that achieves an upper bound on the optimal download cost for arbitrary ε and δ. We show that the optimal download cost of AL-PIR is upper-bounded as D*(ε,δ) ≤ 1+ 1/N−1 − δeε/NK−1−1. Second, we obtain an information-theoretic lower bound on the download cost as D*(ε,δ) ≥ 1 + 1/Neε−1 − δ/(Neε)K−1 −1. The gap analysis between the two bounds shows that our AL-PIR scheme is optimal when ε = 0, i.e., under perfect user privacy and it is optimal within a maximum multiplicative gap of N−e−ε/N−1 for any ε > 0 and δ > 0. [ABSTRACT FROM AUTHOR]

This paper investigates reducing sub-packetization of capacity-achieving schemes for uncoded Storage Constrained Private Information Retrieval (SC-PIR) systems. In the SC-PIR system, a user aims to download one out of K files from N servers while revealing nothing about the identity of the requested file to any individual server, in which the K files are stored at the N servers in an uncoded form and each server can store up to μK equivalent files, where μ is the normalized storage capacity of each server. We first prove that there exists a capacity-achieving SC-PIR scheme for a given storage design if and only if all the packets are stored exactly at M ≜ μN servers for μ such that M = μN ∈ {2,3, . . . ,N}. Then, the optimal sub-packetization for capacity-achieving linear SC-PIR schemes is characterized as the solution to an optimization problem, which is typically hard to solve since it involves non-continuous indicator functions. Moreover, a new notion of array called Storage Design Array (SDA) is introduced for the SC-PIR system. With any given SDA, an associated capacity-achieving SC-PIR scheme is constructed. Next, the SC-PIR schemes that have equal-size packets are investigated. Furthermore, the optimal equal-size sub-packetization among all capacity-achieving linear SC-PIR schemes characterized by Woolsey et al. is proved to be N(M−1)/gcd (N,M), which is achieved by a construction of SDA. Finally, by allowing unequal size of packets, a greedy SDA construction is proposed, where the sub-packetization of the associated SC-PIR scheme is upper bounded by N(M−1)/gcd (N,M). Among all capacity-achieving linear SC-PIR schemes, the sub-packetization is optimal when min{M,N−M}|N or M = N, and within a multiplicative gap min{M,N−M}/gcd (N,M) of the optimal one in general. In particular, for the special case N = d ⋅ M ± 1 where the positive integer d ≥ 2, we propose another SDA construction to obtain lower sub-packetization. [ABSTRACT FROM AUTHOR]

Distracted driving due to smartphone use is one of the key reasons for road accidents. However, the 6G super-heterogeneous network systems and highly differentiated application scenarios require highly elastic and endogenous information services involving the use of smart apps, and related information retrieval by drivers in modern Vehicle-to-People (V2P) Networks. The tension raised due to the conflicting attention requirements of driving and information retrieval can be resolved by designing information retrieval solutions that demand minimal user interaction. In this paper, we construct a Personalized Search Query Generator (PSQG) to reduce driver-mobile interaction during information retrieval in the 6 G era. This system has a query generator and a query recommendation component that update two sets of relationships dynamically: one is the query and the title, another is search and recommendation. The proposed system learns a user's intent based on historical query records and recommends personalized queries, thus reducing the driver-mobile interaction time. We deploy the system into a real search engine and conduct several online experiments. These experiments are conducted using a custom constructed dataset comprising ten million samples. We use the BLEU-score metric and perform A/B testing. The results demonstrate that our system can assist users in making precise queries efficiently. The proposed system can improve drivers’ safety if used in smartphones and other information retrieval systems in vehicles. [ABSTRACT FROM AUTHOR]

The problem of reconstructing a string from its error-prone copies, the trace reconstruction problem, was introduced by Vladimir Levenshtein two decades ago. While there has been considerable theoretical work on trace reconstruction, practical solutions have only recently started to emerge in the context of two rapidly developing research areas: immunogenomics and DNA data storage. In immunogenomics, traces correspond to mutated copies of genes, with mutations generated naturally by the adaptive immune system. In DNA data storage, traces correspond to noisy copies of DNA molecules that encode digital data, with errors being artifacts of the data retrieval process. In this paper, we introduce several new trace generation models and open questions relevant to trace reconstruction for immunogenomics and DNA data storage, survey theoretical results on trace reconstruction, and highlight their connections to computational biology. Throughout, we discuss the applicability and shortcomings of known solutions and suggest future research directions. [ABSTRACT FROM AUTHOR]

The Levenshtein’s channel model for substitution errors is relevant in information retrieval where information is received through many noisy channels. In each of the channels there can occur at most t errors and the decoder tries to recover the information with the aid of the channel outputs. Recently, Yaakobi and Bruck considered the problem where the decoder provides a list instead of a unique output. If the underlying code C ⊆ F2n has error-correcting capability e, we write t = e + ℓ, (ℓ ≥ 1). In this paper, we provide new (constant) bounds on the size of the list. In particular, we give using the Sauer-Shelah lemma the upper bound ℓ + 1 on the list size for large enough n provided that we have a sufficient number of channels. We also show that the bound ℓ + 1 is the best possible. Most of our other new results rely on constant weight codes. [ABSTRACT FROM AUTHOR]

Video question generation is a challenging task in visual information retrieval, which generates questions given a sequence of video frames. The existing methods mainly tackle the problem of single-turn video question generation, but single-turn conversation usually can’t meet the needs of video information acquisition. In this paper, we propose a new framework for single-turn VQG, which introduces attention mechanism to process inference of dialog history. And we introduce selection mechanism to choose from the candidate questions generated by each round of dialog history. In the framework, we leverage a recent video question answering model to predict the answer to the generated question and adopt the answer quality as rewards to fine-tune our model based on a reinforced learning mechanism. We also introduce a new task of multi-turn video question generation (M-VQG), which is generating multiple questions based on dialog history and video information to build conversation step by step. Our method achieves the state-of-the-art performance of the single-turn VQG task on two large-scale datasets, YouTube-Clips and TACoS-MultiLevel, and provides a baseline approach for M-VQG task. [ABSTRACT FROM AUTHOR]

The theory and practice of search results ranking, as currently offered by most web search engines, is older than one might think. The first proposal for a system of ranking was in a JACM paper in 1960. Through the remainder of the twentieth century, extensive research work was done on ranking systems—on devising methods of ranking, on the use of learning methods in association with ranking, and on the comparative evaluation of alternative methods. The web search engines of the tail end of the century made much use of this paper. [ABSTRACT FROM AUTHOR]

This paper concerns the problem of recovering an unknown but structured signal ${x}\in \mathbb {R} ^{n}$ from $m$ -quadratic measurements of the form ${y}_{r}= \left |{\langle {a}_{r}, {x}\rangle }\right |^{{2}}$ for ${r}={1},{2},\ldots, {m}$. We focus on the under-determined setting where the number of measurements is significantly smaller than the dimension of the signal (${m} < < {n}$). We formulate the recovery problem as a nonconvex optimization problem where prior structural information about the signal is enforced through constrains on the optimization variables. We prove the projected gradient descent, when initialized in a neighborhood of the desired signal, converges to the unknown signal at a linear rate. These results hold for any closed constraint set (convex or non-convex) providing convergence guarantees to the global optimum even when the objective function and constraint set are nonconvex. Furthermore, these results hold with a number of measurements that are only a constant factor away from the minimal number of measurements required to uniquely identify the unknown signal. Our results provide the first provably tractable algorithm for this data-poor regime, breaking local sample complexity barriers that have emerged in this paper. In this paper, we utilize and further develop powerful tools for uniform convergence of empirical processes that may have broader implications for rigorous understanding of constrained nonconvex optimization heuristics. [ABSTRACT FROM AUTHOR]

Interval scales are assumed by several basic descriptive statistics, such as mean and variance, and by many statistical significance tests which are daily used in IR to compare systems. Unfortunately, so far, there has not been any systematic and formal study to discover the actual scale properties of IR measures. Therefore, in this paper, we develop a theory of Information Retrieval (IR) evaluation measures, based on the representational theory of measurements, to determine whether and when IR measures are interval scales. We found that common set-based retrieval measures—namely Precision, Recall, and F-measure—always are interval scales in the case of binary relevance while this happens also in the case of multi-graded relevance only when the relevance degrees themselves are on a ratio scale and we define a specific partial order among systems. In the case of rank-based retrieval measures—namely AP, gRBP, DCG, and ERR—only gRPB is an interval scale when we choose a specific value of the parameter $p$ and define a specific total order among systems while all the other IR measures are not interval scales. Besides the formal framework itself and the proof of the scale properties of several commonly used IR measures, the paper also defines some brand new set-based and rank-based IR evaluation measures which ensure to be interval scales. [ABSTRACT FROM AUTHOR]

In this paper, we study two families of codes with availability, namely, private information retrieval (PIR) codes and batch codes. While the former requires that every information symbol has $k$ mutually disjoint recovering sets, the latter imposes this property for each multiset request of $k$ information symbols. The main problem under this paradigm is to minimize the number of redundancy symbols. We denote this value by $r_{P}(n,k)$ and $r_{B}(n,k)$ , for PIR codes and batch codes, respectively, where $n$ is the number of information symbols. Previous results showed that for any constant $k$ , $r_{P}(n,k) = \Theta (\sqrt {n})$ and $r_{B}(n,k)= {\mathcal{ O}}(\sqrt {n}\log (n))$. In this paper, we study the asymptotic behavior of these codes for non-constant $k$ and specifically for $k=\Theta (n^\epsilon)$. We also study the largest value of $k$ such that the rate of the codes approaches 1 and show that for all $\epsilon < 1$ , $r_{P}(n,n^\epsilon) = o(n)$ and $r_{B}(n,n^\epsilon) = o(n)$. Furthermore, several more results are proved for the case of fixed $k$. [ABSTRACT FROM AUTHOR]

Sweep scan is an emerging five-axis inspection technology of retrieving geometric data from free-form surfaces. Compared with the traditional surface inspection by coordinate measuring machine (CMM) that works in a point-by-point manner, sweep scan is able to make the stylus tip continuously sweep at high speed on the surface to inspect, whilst acquiring the 3-D point data accurately and efficiently. However, at present, for an arbitrary free-form surface, it still heavily depends on humans to manually generate a suitable sweep scan path. This paper presents a practical sweep scan path planning method, which can automatically generate an efficient sweep scan path for an arbitrary free-form surface. The resultant sweep scan path is able to cater to the shape of the surface to inspect and the unique kinematic characteristics of the typical five-axis inspection machine, so as to achieve a tremendous increase in inspection efficiency. The experiments performed by us show that when compared with some existing automatic sweep scan path generation algorithms such as the simple zigzag method, the proposed method is able to reduce the total inspection time by as much as seven times. Note to Practitioners—This paper is motivated by the lack of effective automatic sweep scan path planning methods for arbitrary free-form surfaces. Although there is a rich body of five-axis CMM path planning methods for inspection of free-form surfaces, they are mainly designed for the traditional inspection mode, i.e., the point-by-point measurement. Compared with the traditional discrete way of CMM inspection, sweep scan has a quite different inspection mode, which tremendously boosts the inspection efficiency by maintaining the constant contact between the stylus and the surface to inspect. The traditional five-axis inspection path planning methods are no longer applicable to sweep scan. Up to date, only a very handful few of automatic sweep scan path planning methods are reported and they seem to be very difficult to implement and no optimality of inspection efficiency is discussed. We present a practical algorithm for automatic generation of sweep scan paths for inspection of an arbitrary free-form surface. The algorithm is novel in that, by considering both the surface shape and the unique kinematic characteristics of a typical five-axis inspection machine, it tries to globally minimize the total inspection time. In our experiments, the sweep scan paths, generated by the proposed method, are found to outperform that of some traditional simple sweep scan path generation methods such as the zigzag method by a large margin in terms of total inspection time (while the data acquisition accuracy is maintained at the same level). The method is particularly suitable for those industrial parts that are large but relatively smooth, such as windmill blades and automobile panels. [ABSTRACT FROM AUTHOR]

Since the length of microblog texts, such as tweets, is strictly limited to 140 characters, traditional Information Retrieval techniques suffer from the vocabulary mismatch problem severely and cannot yield good performance in the context of microblogosphere. To address this critical challenge, in this paper, we focus on the use of local conceptual word embeddings for enhance microblog retrieval effectiveness. In particular, we propose a novel k-Nearest Neighbor (k NN) based Query Expansion (QE) algorithm to generate words from local word embeddings to expand the original query, which leads to better understanding of the information need. Besides, in order to further satisfy users’ real-time information need, we incorporate temporal evidences into the expansion algorithm, which can boost recent tweets in the retrieval results with respect to a given topic. Experimental results on the official TREC Twitter corpora demonstrate the significant superiority of our approach over baseline methods. [ABSTRACT FROM AUTHOR]

Microblogging services such as Twitter are important, up-to-date, and live sources of information on a multitude of topics and events. An increasing number of systems use such services to detect and analyze events in real-time as they unfold. In this context, we recently proposed ArmaTweet—a system developed in collaboration among armasuisse and the Universities of Oxford and Fribourg to support semantic event detection on Twitter streams. Our experiments have shown that ArmaTweet is successful at detecting many complex events that cannot be detected by simple keyword-based search methods alone. Building up on this work, we explore in this paper several approaches for event detection on microposts. In particular, we describe and compare four different approaches based on keyword search (Plain-Seed-Query), information retrieval (Temporal Query Expansion), Word2Vec word embeddings (Embedding), and semantic retrieval (ArmaTweet). We provide an extensive empirical evaluation of these techniques using a benchmark dataset of about 200 million tweets on six event categories that we collected. While the performance of individual systems varies depending on the event category, our results show that ArmaTweet outperforms the other approaches on five out of six categories, and that a combined approach offers highest recall without adversely affecting precision of event detection. [ABSTRACT FROM AUTHOR]

The support recovery problem consists of determining a sparse subset of variables that is relevant in generating a set of observations. In this paper, we study the support recovery problem in the phase retrieval model consisting of noisy phaseless measurements, which arises in a diverse range of settings such as optical detection, X-ray crystallography, electron microscopy, and coherent diffractive imaging. Our focus is on information-theoretic fundamental limits under an approximate recovery criterion, considering both discrete and Gaussian models for the sparse non-zero entries, along with Gaussian measurement matrices. In both cases, our bounds provide sharp thresholds with near-matching constant factors in several scaling regimes on the sparsity and signal-to-noise ratio. As a key step towards obtaining these results, we develop new concentration bounds for the conditional information content of log-concave random variables, which may be of independent interest. [ABSTRACT FROM AUTHOR]

The problem of $X$ -secure $T$ -private information retrieval from MDS coded storage is studied in this paper, where the user wishes to privately retrieve one out of $K$ independent messages that are distributed over $N$ servers according to an MDS code. It is guaranteed that any group of up to $X$ colluding servers learn nothing about the messages and that any group of up to $T$ colluding servers learn nothing about the identity of desired message. A lower bound of achievable rates is proved by presenting a novel scheme based on cross-subspace alignment and a successive decoding with interference cancellation strategy. For large number of messages $(K\rightarrow \infty)$ the achieved rate, which we conjecture to be optimal, improves upon the best known rates previously reported in the literature by Raviv and Karpuk, and generalizes an achievable rate for MDS-TPIR previously found by Freij-Hollanti et al. that is also conjectured to be asymptotically optimal. The setting is then expanded to allow unresponsive and Byzantine servers. Finally, the scheme is applied to find a new lower convex hull of (download, upload) pairs of secure and private distributed matrix multiplication that generalizes, and in certain asymptotic settings strictly improves upon the best known previous results. [ABSTRACT FROM AUTHOR]

Link similarity is widely applied in measuring the similarity between such objects as Web pages, scientific papers, and social networks. However, there are some deficiencies in the existing methods to measure it. For example, they cannot handle some semantic-similar contents. Their computation may not lead to accurate results in some cases. This paper presents a novel method to do so. It introduces the semantic similarity to calculate the similarity between two given objects, and overcomes the drawback caused by the fact that the existing methods ignore the semantic information of objects. It also gives a novel computation function to make the computing result of similarity more accurate. [ABSTRACT FROM PUBLISHER]

Consider a continuous signal that cannot be observed directly. Instead, one has access to multiple corrupted versions of the signal. The available corrupted signals are correlated because they carry information about the common remote signal. The goal is to reconstruct the original signal from the data collected from its corrupted versions. Known as the indirect or remote reconstruction problem, it has been mainly studied in the literature from an information theoretic perspective. A variant of this problem for a class of Gaussian signals, known as the “Gaussian CEO problem,” has received particular attention; for example, it has been shown that the problem of recovering the remote signal is equivalent with the problem of recovering the set of corrupted signals (separation principle). The information theoretic formulation of the remote reconstruction problem assumes that the corrupted signals are uniformly sampled and the focus is on optimal compression of the samples. On the other hand, in this paper, we revisit this problem from a sampling perspective. More specifically, assuming restrictions on the sampling rate from each corrupted signal, we look at the problem of finding the best sampling locations for each signal to minimize the total reconstruction distortion of the remote signal. In finding the sampling locations, one can take advantage of the correlation among the corrupted signals. The statistical model of the original signal and its corrupted versions adopted in this paper are similar to the one considered for the Gaussian CEO problem; i.e., we restrict to a class of Gaussian signals. Our main contribution is a fundamental lower bound on the reconstruction distortion for any arbitrary nonuniform sampling strategy. This lower bound is valid for any sampling rate. Furthermore, it is tight and matches the optimal reconstruction distortion in low and high sampling rates. Moreover, it is shown that in the low sampling rate region, it is optimal to use a certain nonuniform sampling scheme on all the signals. On the other hand, in the high sampling rate region, it is optimal to uniformly sample all the signals. We also consider the problem of finding the optimal sampling locations to recover the set of corrupted signals, rather than the remote signal. Unlike the information theoretic formulation of the problem in which these two problems were equivalent, we show that they are not equivalent in our setting. Finally, another contribution of this paper is a new reverse majorization inequality that might be of independent interest. [ABSTRACT FROM PUBLISHER]

Conceptual and relational data models of online transaction processing (OLTP) applications are usually created and maintained following the principle of normalization, which implies avoidance of redundancy. Data retrieval from a disk-based normalized relational database often requires complex and inefficient queries that may cause noticeable performance issues when executed on larger volumes of data. Computer professionals sometimes intentionally trade off the strict normal form to optimize data retrieval queries through error-prone manual tuning and denormalization. We propose a fully automatic optimization approach, based on data redundancy, that relies on a formal cost-benefit model. We prove that finding the optimal level of data redundancy, for given workload statistics, is an NP-Complete optimization problem. A detailed reduction of the problem to binary linear programming is presented in the paper. The proposed optimization approach was evaluated using the TPCE benchmark for OLTP systems. The evaluation has shown that the proposed optimization approach is highly scalable, and that it can be efficiently applied to real-life relational data models. [ABSTRACT FROM AUTHOR]

As a challenging task in visual information retrieval, open-ended long-form video question answering automatically generates the natural language answer from the referenced video content according to the given question. However, the existing video question answering works mainly focus on the short-form video, which may be ineffectively applied for long-form video question answering directly, due to the insufficiency of modeling the semantic representation of long-form video content. In this paper, we study the problem of open-ended long-form video question answering from the viewpoint of hierarchical multi-modal conditional adversarial network learning. We propose the hierarchical attentional encoder network to learn the joint representation of long-form video content and given question with adaptive video segmentation. We then devise the reinforced decoder network to generate the natural language answer for open-ended video question answering with multi-modal conditional adversarial network learning. We construct three large-scale open-ended video question answering datasets. The extensive experiments validate the effectiveness of our method. [ABSTRACT FROM AUTHOR]

Private information retrieval (PIR) is the problem of privately retrieving one out of $M$ original files from $N$ severs, i.e., each individual server gains no information on the identity of the file that the user is requesting. Usually, the $M$ files are replicated or encoded by a maximum distance separable (MDS) code and then stored across the $N$ servers. Compared to mere replication, MDS-coded servers can significantly reduce the storage overhead. Particularly, PIR from minimum storage regenerating (MSR) coded servers can simultaneously reduce the repair bandwidth when repairing failed servers. Existing PIR protocols from MSR-coded servers either require large sub-packetization levels or are not capacity-achieving. In this paper, a PIR protocol from MDS array codes is proposed, subsuming PIR from MSR-coded servers as a special case. Particularly, only the case of non-colluding, honest-but-curious servers is considered. The retrieval rate of the new PIR protocol achieves the capacity of PIR from MDS-/MSR-coded servers. By choosing different MDS array codes, the new PIR protocol can have varying advantages when compared with existing protocols, e.g., 1) small sub-packetization, 2) (near-)optimal repair bandwidth, 3) implementable over the binary field $\mathbf {F}_{2}$. [ABSTRACT FROM AUTHOR]

In a Private Information Retrieval (PIR) protocol, a user can download a file from a database without revealing the identity of the file to each individual server. A PIR protocol is called $t$ -private if the identity of the file remains concealed even if $t$ of the servers collude. Graph based replication is a simple technique, which is prevalent in both theory and practice, for achieving robustness in storage systems. In this technique each file is replicated on two or more storage servers, giving rise to a (hyper-)graph structure. In this paper we study private information retrieval protocols in graph based replication systems. The main interest of this work is understanding the collusion structures which emerge in the underlying graph. Our main contribution is a 2-replication scheme which guarantees perfect privacy from acyclic sets in the graph, and guarantees partial-privacy in the presence of cycles. Furthermore, by providing an upper bound, it is shown that the PIR rate of this scheme is at most a factor of two from its optimal value for regular graphs. Lastly, we extend our results to larger replication factors and to graph-based coding, a generalization of graph based replication that induces smaller storage overhead and larger PIR rate in many cases. [ABSTRACT FROM AUTHOR]

Recently, information-theoretic private information retrieval (PIR) from coded storage systems has gained a lot of attention, and a general star product PIR scheme was proposed. In this paper, the star product scheme is adopted, with appropriate modifications, to the case of private (e.g., video) streaming. It is assumed that the files to be streamed are stored on $n$ servers in a coded form, and the streaming is carried out via a convolutional code. The star product scheme is defined for this special case, and various properties are analyzed for two channel models related to straggling and Byzantine servers, both in the baseline case as well as with colluding servers. The achieved PIR rates for the given models are derived and, for the cases where the capacity is known, the first model is shown to be asymptotically optimal, when the number of stripes in a file is large. The second scheme introduced in this work is shown to be the equivalent of block convolutional codes in the PIR setting. For the Byzantine server model, it is shown to outperform the trivial scheme of downloading stripes of the desired file separately without memory. [ABSTRACT FROM AUTHOR]

Fractional repetition (FR) codes form a special class of minimum bandwidth regenerating codes by providing uncoded repairs via a table-based repair model. For a given file size, it is desirable to design FR codes that minimize the reconstruction degree, which is defined as the number of storage nodes required for data retrieval. In this paper, we first consider a lower bound on the reconstruction degree of FR codes obtained by Silberstein and Etzion. We present several families of FR codes that attain this lower bound, which are derived from combinatorial designs and regular graphs. We further provide a new lower bound on the reconstruction degree of FR codes, which is tighter than the existing one. Moreover, we show that for an FR code with reconstruction degree achieving the lower bounds, the corresponding dual code attains upper bounds on the supported file size. [ABSTRACT FROM AUTHOR]

Open-ended long-form video question answering is a challenging task in visual information retrieval, which automatically generates a natural language answer from the referenced long-form video contents according to a given question. However, the existing works mainly focus on short-form video question answering, due to the lack of modeling semantic representations from long-form video contents. In this paper, we introduce a dynamic hierarchical reinforced network for open-ended long-form video question answering, which employs an encoder–decoder architecture with a dynamic hierarchical encoder and a reinforced decoder. Concretely, we first propose a frame-level dynamic long-short term memory (LSTM) network with binary segmentation gate to learn frame-level semantic representations according to the given question. We then develop a segment-level highway LSTM network with a question-aware highway gate for segment-level semantic modeling. Furthermore, we devise the reinforced decoder with a hierarchical attention mechanism to generate natural language answers. We construct a large-scale long-form video question answering dataset. The extensive experiments on the long-form dataset and another public short-form dataset show the effectiveness of our method. [ABSTRACT FROM AUTHOR]

Wafer map defect pattern contains the critical information about semiconductor manufacturing, effective defect analysis technology can improve the yield of products. This paper develops a wafer defect pattern recognition and analysis method based on convolutional neural network (CNN). We build an 8-layer CNN model to inspect wafer map defect and a 13-layer model to classify defect patterns. To analyze the defects, we first extract features based on the classification network, then perform PCA dimensionality reduction and similarity ranking, we infer the root causes of tested samples according to the retrieved wafer maps. In particular, we analyze the impacts of different network layers and feature dimensions on image retrieval performance, it turns out that the appropriate dimensionality reduction can increase the accuracy and speed of wafer map retrieval. The models are trained and tested on the WM-811K wafer map dataset, which are collected from real wafer maps. The experimental results show that the proposed method is able to identify common wafer defect patterns and analyze the root causes accurately and effectively. [ABSTRACT FROM AUTHOR]