Query compilation in PostgreSQL by specialization of the DBMS source code

This paper describes the development of a query compiler for the PostgreSQL DBMS based on automatic code specialization methods; these methods allow one to avoid the development and support difficulties typical for classical query compilers by dividing the compiler development problem into two independent subproblems: reduction of overhead costs and implementation of algorithmic improvements. We assert that this decomposition facilitates the solution of both the subproblems: the cost reduction can be automated, while the algorithmic improvements can be implemented in the interpreter in the DBMS implementation language. This paper presents methods for online and offline specialization, considers specifics of specialization and binding-time analysis of the PostgreSQL source code, and describes the transition to a push model of execution.     

The Faces of Facebookers: Investigating Social Enhancement and Social Compensation Hypotheses; Predicting Facebook™ and Offline Popularity from Sociability and Self‐Esteem,and Mapping the Meanings of Popularity with Semantic Networks

This research investigates two competing hypotheses from the literature: 1) the Social Enhancement (“Rich Get Richer”) hypothesis that those more popular offline augment their popularity by increasing it on Facebook?, and 2) the “Social Compensation” (“Poor Get Richer”) hypothesis that users attempt to increase their Facebook? popularity to compensate for inadequate offline popularity. Participants (n= 614) at a large, urban university in the Midwestern United States completed an online survey. Results are that a subset of users, those more extroverted and with higher self‐esteem, support the Social Enhancement hypothesis, being more popular both offline and on Facebook?. Another subset of users, those less popular offline, support the Social Compensation hypotheses because they are more introverted, have lower self‐esteem and strive more to look popular on Facebook?. Semantic network analysis of open‐ended responses reveals that these two user subsets also have different meanings for offline and online popularity. Furthermore, regression explains nearly twice the variance in offline popularity as in Facebook? popularity, indicating the latter is not as socially grounded or defined as offline popularity.     

An investigation of Jones optimality and BTI-universal specializers

Jones optimality implies that a program specializer is strong enough to remove an entire level of self-interpretation. This paper argues that Jones optimality, which was originally devised as a criterion for self-applicable specializers, plays a fundamental role in the use of a binding-time improvement prepass prior to specialization. We establish that, regardless of the binding-time improvements applied to a subject program (no matter how extensively), a specializer that is not Jones-optimal is strictly weaker than a specializer that is Jones-optimal. We describe the main approaches that increase the strength of a specializer without requiring its modification, namely incremental specialization and the interpretive approach, and show that they are equally powerful when the specializer is bti-universal. Since this includes the generation of program specializers from interpreters, the theoretical possibility of bootstrapping powerful specializers is established.     

An Automatic Program Generator for Multi-Level Specialization

Program specialization can divide a computation into several computation stages. This paper investigates the theoretical limitations and practical problems of standard specialization tools, presents multi-level specialization, and demonstrates that, in combination with the cogen approach, it is far more practical than previously supposed. The program generator which we designed and implemented for a higher-order functional language converts programs into very compact multi-level generating extensions that guarantee fast successive specialization. Experimental results show a remarkable reduction of generation time and generator size compared to previous attempts of multi-level specialization by self-application. Our approach to multi-level specialization seems well-suited for applications where generation time and program size are critical.     

The essence of eta-expansion in partial evaluation

Selective eta-expansion is a powerful binding-time improvement,i.e., a source-program modification that makes a partial evaluator yield better results. But like most binding-time improvements, the exact problem it solves and the reason why have not been formalized and are only understood by few.In this paper, we describe the problem and the effect of eta-redexes in terms of monovariant binding-time propagation: eta-redexes preserve the static data flow of a source program by interfacingstatic higher-order values in dynamic contexts anddynamic higher-order values in static contexts. They contribute to twodistinct binding-time improvements.We present two extensions of Gomard's monovariant binding-time analysis for the pure -calculus. Our extensions annotateand eta-expand -terms. The first one eta-expands static higher-order values in dynamic contexts. The second also eta-expands dynamic higher-order values in static contexts.As a significant application, we show that our first binding-time analysis suffices to reformulate the traditional formulation of a CPS transformation into a modern one-pass CPS transformer. This binding-time improvement is known, but it is still left unexplained in contemporary literature,e.g., about cps-based partial evaluation.We also outline the counterpart of eta-expansion for partially static data structures.     

Partial evaluation in parallel

Partially evaluating a procedural program amounts to building a series of mutually-recursive specialized procedures. When a procedure call in the source program gets specialized into a residual call, the called procedure needs to be processed to occur in the residual program. Because the order of procedure definitions in the residual program is immaterial, it does not matter in which order these two events — building the residual call and building the residual procedure — are scheduled. Therefore, partial evaluation offers a basic opportunity for an MIMD type of parallelism with shared global memory where in essence, the mutually-recursive specialized procedures are built in parallel as specialization points are met and the relation binding source and residual procedures is globalized, to preserve its uniqueness.We have translated a sequential partial evaluator written in T (a dialect of Scheme) into Mul-T (a parallel extension of T) by adding one semaphore with each specialization point and one future to construct the residual procedure in parallel with the current specialization. The resulting parallel partial evaluator has been observed to be faster than the sequential one in proportion to the size of the source program and to the number of specialized procedures in the residual program.Our sequential partial evaluator is self-applicable. Because the semaphores and the future are run-time operations, our parallel partial evaluator is still self-applicable. In principle it can be and in practice we have used it to generate parallel compilers, i.e., specializers dedicated to an interpreter and processing its static and dynamic semantics in parallel, non trivially. Again, parallelism in dedicated specializers is determined by the size of the source program and the number of specialized procedures in the residual program.This work was supported by Darpa under Grant N00014-88-k-0573.This work was carried out during a summer visit to Yale University in 1990. This paper was written at Kansas State University and completed during a spring visit at Carnegie Mellon University in 1993.     

Partial Evaluation of the Euclidean Algorithm, Revisited

The usual formulation of the Euclidean Algorithm is not well-suited to be specialized with respect to one of its arguments, at least when using offline partial evaluation. This has led Danvy and Goldberg to reformulate it using bounded recursion. In this article, we show how The Trick can be used to obtain a formulation of the Euclidean Algorithm with good binding-time separation. This formulation of the Euclidean Algorithm specializes effectively using standard offline partial evaluation.     

Class Constrained Bin Covering

We study the following variant of the bin covering problem. We are given a set of unit sized items, where each item has a color associated with it. We are given an integer parameter k≥1 and an integer bin size B≥k. The goal is to assign the items (or a subset of the items) into a maximum number of subsets of at least B items each, such that in each such subset the total number of distinct colors of items is at least k. We study both the offline and the online variants of this problem. We first design an optimal polynomial time algorithm for the offline problem. For the online problem we give a lower bound of 1+H _k−1 (where H _k−1 denotes the (k−1)-th harmonic number), and an O(k)-competitive algorithm. Finally, we analyze the performance of the natural heuristic First fit.     

Binding-time analysis for Standard ML

We present an efficient base algorithm for binding-time analysis based on constraint solving and the union-find algorithm. In practice it has been used to handle all of Standard ML except modules and we show the principles of how constraints can be used for binding-time analysis of Standard ML; in particular we show how to binding-time analyse nested pattern matching. To the best of our knowledge no previous binding-time analysis has treated nested pattern matching.The present work was conducted while the author was at DIKU.     

Oracle-Based Partial Evaluation

We present Oracle-Based Partial Evaluation (OBPE), a novel approach to on-line Partial Evaluation (PE) which decides the control strategy to use for each call pattern by using an oracle function which compares the results of specializing such call pattern w.r.t. a set of strategies. Our proposal is motivated by Poly-Controlled Partial Evaluation (PCPE), which allows using different control strategies for different call patterns. Given a set of control strategies, the best PCPE specialized programs outperform the specialized programs obtained by traditional PE for any of the control strategies in , especially when resource-aware specialization is performed. Unfortunately, computing all PCPE specialized programs and then choosing a posteriori the best one is too costly in practice. In contrast, in OBPE a single specialized program is computed. We have developed an empirical oracle whose parameters are approximated from a set of training data, by using constraint logic programming. Our experimental results show that the additional cost of OBPE when compared with traditional PE is a constant factor and that, at least in our experiments, OBPE obtains significantly better specializations. We argue that our proposal is relevant in practice and introduces clear improvements over standard PE. Our work is developed in the context of logic programs, though the ideas are in principle of interest to the PE of any programming language.     

Empirical investigation of customers’ channel extension behavior: Perceptions shift toward the online channel

An increasing number of traditional (offline) firms are opening up their online sales channels. However, a number of them are finding it difficult to increase the utilization of their online channels from their existing customers. The purpose of the current study is to identify factors that influence customers channel extension from the offline to online channel and to understand how these factors influence customers’ behavior towards online channel extension. Drawing on the theory of entitativity formulated by Campbell, we propose a research model of customers channel extension by focusing on the shift of perception from offline to the online channel. The data for the study is collected from a large bank in China. The structural equation modeling analysis results indicate that perceived offline service quality influences perceived online service quality both directly as well as indirectly through perceived entitativity. Perceived online service quality, in turn influences customers’ behavior towards the online channel extension. The results also demonstrate that self-efficacy for change directly influences behavior towards the online channel extension, and it also has an important moderating influence on relationship between perceived offline service quality and perceived online service quality. Theoretical and practical implications of the findings are discussed.     

Communication Communities or “CyberGhettos?”: A Path Analysis Model Examining Factors that Explain Selective Exposure to Blogs1

This study used an online panel of Internet users to examine the degree to which blog users practice selective exposure when seeking political information. The research employed a path analysis model to explore the extent to which exposure to offline and online discussion of political issues, and offline and online media use, as well as political variables and demographic factors, predict an individual's likelihood to engage in selective exposure to blogs. The findings indicate that respondents did practice selective exposure to blogs, predominantly those who are heavy blog users, politically active both online and offline, partisan, and highly educated.     

Automatic and personalized recommendation of TV program contents using sequential pattern mining for smart TV user interaction

Due to the excessive number of TV program contents available at user’s side, efficient access to the preferred TV program content becomes a critical issue for smart TV user interaction. In this paper, we propose an automatic recommendation scheme of TV program contents in sequence using sequential pattern mining (SPM). Motivation of sequential TV program recommendation is based on TV viewer’s behaviors for watching multiple TV program contents in a row. A sequence of TV program contents for recommendation to a target user is constructed based on the features such as an occurrence and net occurrence of frequently watched TV program contents from the similar user group to which the target user belongs. Three types of SPM methods are presented—offline, online and hybrid SPM. To extract sequential patterns of preferably watched TV program contents, we propose a preference weighted normalized modified retrieval rank (PW-NMRR) metric for similar user clustering. In the offline SPM method, we effectively construct the sequential patterns for recommendation using a projection method, which yields good performance for relatively longer sequential patterns. The online SPM method mines sequential patterns online by effectively reflecting the recent preference characteristics of users for TV program contents, which is effective for short-sequence recommendation. The hybrid SPM method combines the offline and online SPM methods. The maximum precisions of 0.877, 0.793 and 0.619 for length-1, -2 and -3 sequence recommendations are obtained from the online, hybrid and offline SPM methods, respectively.     

Online Dynamic Programming Speedups

Consider the dynamic program h(n)=min _1≤j≤n a(n,j), where a(n,j) is some formula that may (online) or may not (offline) depend on the previously computed h(i), for i<n. The goal is to compute all h(n), for 1≤n≤N. It is well known that, if a(n,j) satisfy the Monge property, then the SMAWK algorithm (Aggarwal et al., Algorithmica 2(1):195–208, 1987) can solve the offline problem in O(N) time; a Θ(N) speedup over the naive algorithm. In this paper we extend this speedup to the online case, that is, to compute h(n) in the order n=1,2,…,N when (i) we do not know the values of a(n′,j) for n′>n before h(n) has been computed and (ii) do not know the problem size N in advance. We show that if a(n,j) satisfy a stronger, but sometimes still natural, property than the Monge one, then each h(n) can be computed in online fashion in O(1) amortized time. This maintains the speedup online, in the sense that the total time to compute all h(n) is O(N). We also show how to compute each h(n) in the worst case O(log N) time, while maintaining the amortized time bound. For a(n,j) satisfying our stronger property, our algorithm is also simpler than the standard SMAWK algorithm for solving the offline case. We illustrate our technique on two examples from the literature; the first is the D-median problem on a line, and the second comes from mobile wireless paging. The research of the first author was partially supported by the NSF program award CNS-0626606; the research of the second and third authors was partially supported by Hong Kong RGC CERG grant HKUST6312/04E.     

Some Issues in Analysis and Specialization of Modular Ciao-Prolog Programs

Separating programs into modules is a well-known technique which has proven very useful in program development and maintenance. Starting by introducing a number of possible scenarios, in this paper we study different issues which appear when developing analysis and specialization techniques for modular logic programming. We discuss a number of design alternatives and their consequences for the different scenarios considered and describe where applicable the decisions made in the Ciao system analyzer and specializer. In our discussion we use the module system of Ciao Prolog. This is both for concreteness and because Ciao Prolog is a second-generation Prolog system which has been designed with global analysis and specialization in mind, and which has a strict module system. The aim of this work is not to provide a theoretical basis on modular analysis and specialization, but rather to discuss some interesting practical issues.The authors would like to thank Francisco Bueno for many interesting discussions on analysis of modular programs, and the anonymous referees for their constructive comments. This work was funded in part by Spanish CICYT projects TIC99-1151 EDIPIA and TIC97-1640-CE.     

On the degeneration of program generators by program composition

One of the main discoveries in the seventies was that the concept of a generating extension covers a very wide class of apparently different program generators. Program specialization, or partial evaluation, is powerful because it provides uniform techniques for the automatic implementation of generating extensions from ordinary programs. The Futamura projections stand as the cornerstone of the development of program specialization. This paper takes the idea of the Futamura projections further. Threedegeneration projections are formulated which tell us how to achieve the reverse goal by program composition, namely turning a generating extension into an ordinary program. The fact that program composition can invert the effect of program specialization shows that these projections are dual in a sense. The degeneration projections complete a missing link between programs and generating extensions and allow for novel applications of program transformation.     

Action semantics-directed prototyping

We present a methodology for compiler synthesis based on Mosses-Watt's action semantics. Each action in action semantics notation is assigned specific “analysis functions”, such as a typing function and a binding-time function. When a language is given an action semantics, the typing and binding-time functions for the individual actions compose into typing and binding-time analyses for the language; these are implemented as the type checker and static semantics processor, respectively, in the synthesized compiler. Other analyses can be similarly formalized and implemented. We show a sample language semantics and its synthesized compiler, and we describe the compiler synthesizer that we have developed.     

Efficient online/offline identity-based signature for wireless sensor network

In this paper, we present an online/offline identity-based signature scheme for the wireless sensor network (WSN). We argue that due to significant reduction in costs of computation and storage, our scheme is particularly suitable for the WSN environment with severely constrained resources. One of the interesting features of our scheme is that it provides multi-time usage of the offline storage, which allows the signer to re-use the offline pre-computed information in polynomial time, in contrast to one-time usage in all previous online/offline signature schemes. As evidence of the practicality and feasibility of our scheme to be used in the WSN environment, we provide an actual implementation result of our scheme on the MicaZ platform.     

基于人工智能的患者智能问诊服务应用平台

目的:通过建设智能问诊服务平台,快速定位适应症患者,减轻医院线下诊疗压力、提高医护工作效率、提升患者就医的获得感。方法:通过利用机器学习、自然语言处理、知识图谱等人工智能技术,利用学习提供的权威临床疾病资料,构建专业临床知识库,促进研制推理逻辑算法,开发了线上患者智能问诊系统。结果:通过智能问诊平台的应用,实现了线上线下相结合的就医新模式、打破了患者与医护沟通的壁垒、实现了指尖就医减少了患者不必要的就医成本。结论:智能问诊平台的应用,用智慧化解"看病烦"与"就医繁"、跨时空均衡配置医疗资源。     

Scheduling jobs with equal processing times subject to machine eligibility constraints

We consider the problem of nonpreemptively scheduling a set of n jobs with equal processing times on m parallel machines so as to minimize the makespan. Each job has a prespecified set of machines on which it can be processed, called its eligible set. We consider the most general case of machine eligibility constraints as well as special cases of nested and inclusive eligible sets. Both online and offline models are considered. For offline problems we develop optimal algorithms that run in polynomial time, while for online problems we focus on the development of optimal algorithms of a new and more elaborate structure as well as approximation algorithms with good competitive ratios.