More Like this

1. Tangent-CFT: An Embedding Model for Mathematical Formulas

   https://doi.org/10.1145/3341981.3344235  

   Mansouri, Behrooz; Rohatgi, Shaurya; Oard, Douglas W.; Wu, Jian; Giles, C. Lee; Zanibbi, Richard (January 2019, ICTIR '19 Proceedings of the 2019 ACM SIGIR International Conference on Theory of Information Retrieval)

   When searching for mathematical content, accurate measures of formula similarity can help with tasks such as document ranking, query recommendation, and result set clustering. While there have been many attempts at embedding words and graphs, formula embedding is in its early stages. We introduce a new formula em- bedding model that we use with two hierarchical representations, (1) Symbol Layout Trees (SLTs) for appearance, and (2) Operator Trees (OPTs) for mathematical content. Following the approach of graph embeddings such as DeepWalk, we generate tuples represent- ing paths between pairs of symbols depth-first, embed tuples using the fastText n-gram embedding model, and then represent an SLT or OPT by its average tuple embedding vector. We then combine SLT and OPT embeddings, leading to state-of-the-art results for the NTCIR-12 formula retrieval task. Our fine-grained holistic vector representations allow us to retrieve many more partially similar for- mulas than methods using structural matching in trees. Combining our embedding model with structural matching in the Approach0 formula search engine produces state-of-the-art results for both fully and partially relevant results on the NTCIR-12 benchmark. Source code for our system is publicly available. 

   more » « less
2. A Deeper Investigation of the Importance of Wikipedia Links to Search Engine Results

   https://doi.org/10.1145/3449078  

   Vincent, Nicholas; Hecht, Brent (April 2021, Proceedings of the ACM on Human-Computer Interaction)

   A growing body of work has highlighted the important role that Wikipedia's volunteer-created content plays in helping search engines achieve their core goal of addressing the information needs of hundreds of millions of people. In this paper, we report the results of an investigation into the incidence of Wikipedia links in search engine results pages (SERPs). Our results extend prior work by considering three U.S. search engines, simulating both mobile and desktop devices, and using a spatial analysis approach designed to study modern SERPs that are no longer just "ten blue links". We find that Wikipedia links are extremely common in important search contexts, appearing in 67-84% of desktop SERPs for common and trending queries, but less often for medical queries. Furthermore, we observe that Wikipedia links often appear in "Knowledge Panel" SERP elements and are in positions visible to users without scrolling, although Wikipedia appears less often and in less prominent positions on mobile devices. Our findings reinforce the complementary notions that (1) Wikipedia content and research has major impact outside of the Wikipedia domain and (2) powerful technologies like search engines are highly reliant on free content created by volunteers. 

   more » « less
3. Partisan search behavior and Google results in the 2018 U.S. midterm elections

   https://doi.org/10.1080/1369118X.2020.1764605  

   Trielli, Daniel; Diakopoulos, Nicholas (May 2020, Information, Communication & Society)

   This research shows that members of different ideological groups in the United States can use different search terms when looking for information about political candidates, but that difference is not enough to yield divergent search results on Google. Search engines are central in information seeking during elections, and have important implications for the distribution of information and, by extension, for democratic society. Using a method involving surveys, qualitative coding, and quantitative analysis of search terms and search results, we show that the sources of information that are returned by Google for both liberal and conservative search terms are strongly correlated. We collected search terms from people with different ideological positions about Senate candidates in the 2018 midterm election from the two main parties in the U.S., in three large and politically distinct states: California, Ohio, and Texas. We then used those search terms to scrape web results and analyze them. Our analysis shows that, in terms of the differences arising from individual search term choices, Google results exhibit a mainstreaming effect that partially neutralizes differentiation of search behaviors, by providing a set of common results, even to dissimilar searches. Based on this analysis, this article offers two main contributions: first, in the development of a method for determining group-level differences based on search input bias; and second, in demonstrating how search engines respond to diverse information seeking behavior and whether that may have implications for public discourse. 

   more » « less
4. A trace inequality of Ando, Hiai, and Okubo and a monotonicity property of the Golden–Thompson inequality

   https://doi.org/10.1063/5.0091111  

   Carlen, Eric A.; Lieb, Elliott H. (June 2022, Journal of Mathematical Physics)

   The Golden–Thompson trace inequality, which states that Tr  e H+ K ≤ Tr  e H e K , has proved to be very useful in quantum statistical mechanics. Golden used it to show that the classical free energy is less than the quantum one. Here, we make this G–T inequality more explicit by proving that for some operators, notably the operators of interest in quantum mechanics, H = Δ or [Formula: see text] and K = potential, Tr  e H+(1− u) K e uK is a monotone increasing function of the parameter u for 0 ≤ u ≤ 1. Our proof utilizes an inequality of Ando, Hiai, and Okubo (AHO): Tr  X s Y t X 1− s Y 1− t ≤ Tr  XY for positive operators X, Y and for [Formula: see text], and [Formula: see text]. The obvious conjecture that this inequality should hold up to s + t ≤ 1 was proved false by Plevnik [Indian J. Pure Appl. Math. 47, 491–500 (2016)]. We give a different proof of AHO and also give more counterexamples in the [Formula: see text] range. More importantly, we show that the inequality conjectured in AHO does indeed hold in the full range if X, Y have a certain positivity property—one that does hold for quantum mechanical operators, thus enabling us to prove our G–T monotonicity theorem. 

   more » « less
5. An Ultra-Fast and Parallelizable Algorithm for Finding $$k$$-Mismatch Shortest Unique Substrings

   https://doi.org/10.1109/TCBB.2020.2968531  

   Allen, Daniel R.; Thankachan, Sharma V.; Xu, Bojian (January 2021, IEEE/ACM Transactions on Computational Biology and Bioinformatics)

   null (Ed.)

   This paper revisits the k-mismatch shortest unique substring finding problem and demonstrates that a technique recently presented in the context of solving the k-mismatch average common substring problem can be adapted and combined with parts of the existing solution, resulting in a new algorithm which has expected time complexity of O(n log^k n), while maintaining a practical space complexity at O(kn), where n is the string length. When , which is the hard case, our new proposal significantly improves the any-case O(n^2) time complexity of the prior best method for k-mismatch shortest unique substring finding. Experimental study shows that our new algorithm is practical to implement and demonstrates significant improvements in processing time compared to the prior best solution's implementation when k is small relative to n. For example, our method processes a 200 KB sample DNA sequence with k=1 in just 0.18 seconds compared to 174.37 seconds with the prior best solution. Further, it is observed that significant portions of the adapted technique can be executed in parallel, using two different simple concurrency models, resulting in further significant practical performance improvement. As an example, when using 8 cores, the parallel implementations both achieved processing times that are less than 1/4 of the serial implementation's time cost, when processing a 10 MB sample DNA sequence with k=2. In an age where instances with thousands of gigabytes of RAM are readily available for use through Cloud infrastructure providers, it is likely that the trade-off of additional memory usage for significantly improved processing times will be desirable and needed by many users. For example, the best prior solution may spend years to finish a DNA sample of 200MB for any , while this new proposal, using 24 cores, can finish processing a sample of this size with k=1 in 206.376 seconds with a peak memory usage of 46 GB, which is both easily available and affordable on Cloud. It is expected that this new efficient and practical algorithm for k-mismatch shortest unique substring finding will prove useful to those using the measure on long sequences in fields such as computational biology. We also give a theoretical bound that the k-mismatch shortest unique substring finding problem can be solved using O(n log^k n) time and O(n) space, asymptotically much better than the one we implemented, serving as a new discovery of interest. 

   more » « less